Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs. (English) Zbl 1223.05195
Summary: There are numerous means for measuring the closeness to planarity of a graph such as crossing number, splitting number, and a variety of thickness parameters. We focus on the classical concept of the thickness of a graph, and we add to earlier work [J. Graph Theory 57, No. 3, 198–214 (2008;
Zbl 1136.05044)]. In particular, we offer new 9-critical thickness-two graphs on 17, 25, and 33 vertices, all of which provide counterexamples to a conjecture on independence ratio of Albertson; we investigate three classes of graphs, namely singly and doubly outerplanar graphs, and cloned planar graphs. We give a sharp upper bound for the largest chromatic number of the cloned planar graphs, and we give upper and lower bounds for the largest chromatic number of the former two classes.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C75 | Structural characterization of families of graphs |
| 68R10 | Graph theory (including graph drawing) in computer science |
Citations:
Zbl 1136.05044References:
| [1] | Appel, K., Haken, W.: Supplement to: ”Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429–490) by Appel and Haken; ”II. Reducibility” (ibid. 21 (1977), no. 3, 491–567) by Appel, Haken and J. Koch. Illinois J. Math., 21(3), 1–251. (microfiche supplement) (1977) · Zbl 0387.05009 |
| [2] | Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. Part II. Reducibility. Illinois J. Math., 21, 491–567 (1977) · Zbl 0387.05010 |
| [3] | Albertson, M.O.: A conjecture on the independence ratio of thickness-two graphs. (Personal communication). |
| [4] | Boutin, D.L., Gethner, E., Sulanke, T.: Thickness-two graphs. I. New nine-critical graphs, permuted layer graphs, and Catlin’s graphs. J. Graph Theory, 57(3), 198–214 (2008) · Zbl 1136.05044 |
| [5] | Battle, J., Harary, F., Kodama, Y.: Every planar graph with nine points has a nonplanar complement. Bull. Amer. Math. Soc., 68, 569–571 (1962) · Zbl 0114.14602 |
| [6] | Gardner, M.: Mathematical games. Sci. Amer., 242, 14–19 February 1980 |
| [7] | Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, (1990) · Zbl 0411.68039 |
| [8] | Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In STOC ’74: Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47–63, ACM Press New York, NY, USA, 1974. · Zbl 0338.05120 |
| [9] | Guy, R.K., Nowakowski, R.J.: The outerthickness & outercoarseness of graphs. I. The complete graph & the n-cube. In: Topics in combinatorics and graph theory (Oberwolfach, 1990), pp. 297–310. Physica, Heidelberg (1990) · Zbl 0742.05069 |
| [10] | Guy, R.K., Nowakowski, R.J.: The outerthickness & outercoarseness of graphs. II. The complete bipartite graph. In: Contemporary methods in graph theory, pp. 313–322. Bibliographisches Inst., Mannheim (1990) · Zbl 0731.05014 |
| [11] | Hajós, G.: Über eine Konstruktion nicht n-färbbarer Graphen. Wiss. Z. Martin Luther Univ., 10, 116–117 (1961) |
| [12] | Hutchinson, J.P.: Coloring ordinary maps, maps of empires and maps of the moon. Math. Mag., 66(4), 211–226 (1993) · Zbl 0804.05037 |
| [13] | Jensen, T.R., Royle, G.F.: Hajós constructions of critical graphs. J. Graph Theory, 30(1), 37–50 (1999) · Zbl 0924.05026 |
| [14] | Kocay, W., Kreher, D.L.: Graphs, algorithms, and optimization. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL (2005) · Zbl 1079.05001 |
| [15] | Koester, G.: 4-critical 4-valent planar graphs constructed with crowns. Math. Scand., 67(1), 15–22 (1990) · Zbl 0723.05056 |
| [16] | Mansfield, A.: Determining the thickness of graphs is NP-hard. Math. Proc. Cambridge Philos. Soc., 93(1), 9–23 (1983) · Zbl 0503.68048 |
| [17] | McKay, B.D.: Groups and Graphs: software package for graphs, digraphs, graph embeddings, projective configurations, polyhedra, convex hulls, combinatorial designs, automorphism groups, and fractals. Website, 1997-2007. http://www.paddle.mb.ca/G&G/G&G.html/ |
| [18] | Ringel, G.: Färbungsprobleme auf Flächen und Graphen, volume 2 of Mathematische Monographien. VEB Deutscher Verlag der Wissenschaften, Berlin (1959) · Zbl 0088.39601 |
| [19] | Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: A new proof of the four-colour theorem. Electron. Res. Announc. Amer. Math. Soc., 2(1), 17–25 (electronic) (1996) · Zbl 0865.05039 |
| [20] | Sulanke, T.: Decomposing graphs into triangulations using random diagonal flips. (in preparation) |
| [21] | Tutte, W.T.: The non-biplanar character of the complete 9-graph. Canad. Math. Bull., 6, 319–330 (1963) · Zbl 0113.38803 |
| [22] | West, D.B.: Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ, second edition (2001) · Zbl 0992.83079 |
| [23] | Wilson, R.: Four colors suffice. Princeton University Press, Princeton, NJ, 2002. How the map problem was solved · Zbl 1030.05041 |
| [24] | Wolfram, S.: Wolfram Research, Inc: Mathematica. Website, 1997-2007. http://www.wolfram.com |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
