Complete colorings of planar graphs. (English) Zbl 1405.05051
Summary: In this paper, we study the achromatic and the pseudoachromatic numbers of planar and outerplanar graphs as well as planar graphs of girth 4 and graphs embedded on a surface. We give asymptotically tight results and lower bounds for maximal embedded graphs.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
Keywords:
achromatic number; pseudoachromatic number; outerplanar graphs; thickness; outerthickness; girth-thickness; graphs embeddingsReferences:
| [1] | Aichholzer, O.; Araujo-Pardo, G.; García-Colín, N.; Hackl, T.; Lara, D.; Rubio-Montiel, C.; Urrutia, J., Geometric achromatic and pseudoachromatic indices, Graphs Combin., 32, 2, 431-451 (2016) · Zbl 1339.05105 |
| [2] | Alekseev, V. B.; Gončakov, V. S., The thickness of an arbitrary complete graph, Mat. Sb. (NS), 101, 143, 212-230 (1976), (2) · Zbl 0344.05140 |
| [3] | Araujo-Pardo, G.; Montellano-Ballesteros, J. J.; Rubio-Montiel, C.; Strausz, R., On the pseudoachromatic index of the complete graph II, Bol. Soc. Mat. Mexicana (3), 20, 1, 17-28 (2014) · Zbl 1306.05048 |
| [4] | Araujo-Pardo, G.; Montellano-Ballesteros, J. J.; Rubio-Montiel, C.; Strausz, R., On the pseudoachromatic index of the complete graph III, Graphs Combin., 34, 2, 277-287 (2018) · Zbl 1384.05081 |
| [5] | Araujo-Pardo, G.; Rubio-Montiel, C., Pseudoachromatic and connected-pseudoachromatic indices of the complete graph, Discrete Appl. Math., 231, 60-66 (2017) · Zbl 1369.05060 |
| [6] | Balogh, J.; Hartke, S. G.; Liu, Q.; Yu, G., On the first-fit chromatic number of graphs, SIAM J. Discrete Math., 22, 3, 887-900 (2008) · Zbl 1180.05042 |
| [7] | 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 |
| [8] | Beineke, L. W.; Harary, F., On the thickness of the complete graph, Bull. Amer. Math. Soc., 70, 618-620 (1964) · Zbl 0123.39903 |
| [9] | Beineke, L. W.; Harary, F., The thickness of the complete graph, Canad. J. Math., 17, 850-859 (1965) · Zbl 0135.42104 |
| [10] | Bhave, V. N., On the pseudoachromatic number of a graph, Fund. Math., 102, 3, 159-164 (1979) · Zbl 0396.05021 |
| [11] | Bollobás, B.; Reed, B.; Thomason, A., An extremal function for the achromatic number, (Graph Structure Theory. Graph Structure Theory, (Seattle, WA, 1991). Graph Structure Theory. Graph Structure Theory, (Seattle, WA, 1991), Contemp. Math., vol. 147 (1993), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 161-165 · Zbl 0787.05053 |
| [12] | Chartrand, G.; Zhang, P., (Chromatic Graph Theory. Chromatic Graph Theory, Discrete Mathematics and its Applications (Boca Raton) (2009), CRC Press: CRC Press Boca Raton, FL) · Zbl 1169.05001 |
| [13] | Diestel, R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics (2005), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1074.05001 |
| [14] | Francis, G. K.; Weeks, J. R., Conway’s ZIP proof, Amer. Math. Monthly, 106, 5, 393-399 (1999) · Zbl 0991.57021 |
| [15] | Gupta, R. P., Bounds on the chromatic and achromatic numbers of complementary graphs, (Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Comb., 1968) (1969), Academic Press: Academic Press New York), 229-235 · Zbl 0209.55004 |
| [16] | Guy, R. K., Outerthickness and outercoarseness of graphs, (Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973). Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973), London Math. Soc. Lecture Note Ser., vol. 13 (1974), Cambridge Univ. Press: Cambridge Univ. Press London), 57-60 · Zbl 0293.05108 |
| [17] | Guy, R. K.; Nowakowski, R. J., The outerthickness & outercoarseness of graphs. I. The complete graph & the \(n\)-cube, (Topics in Combinatorics and Graph Theory. Topics in Combinatorics and Graph Theory, (Oberwolfach, 1990) (1990), Physica, Heidelberg), 297-310 · Zbl 0742.05069 |
| [18] | Hara, S.; Nakamoto, A., Achromatic numbers of maximal outerplanar graphs, Yokohama Math. J., 49, 2, 181-186 (2002) · Zbl 1004.05026 |
| [19] | Harary, F.; Hedetniemi, S.; Prins, G., An interpolation theorem for graphical homomorphisms, Port. Math., 26, 453-462 (1967) · Zbl 0187.20903 |
| [20] | Hell, P.; Miller, D. J., Graph with given achromatic number, Discrete Math., 16, 3, 195-207 (1976) · Zbl 0345.05113 |
| [21] | Nishizeki, T.; Baybars, I., Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Math., 28, 3, 255-267 (1979) · Zbl 0425.05032 |
| [22] | Ore, O., (The Four-Color Problem. The Four-Color Problem, Pure and Applied Mathematics, vol. 27 (1967), Academic Press: Academic Press New York-London) · Zbl 0149.21101 |
| [23] | Rubio-Montiel, C., The 4-girth-thickness of the complete graph, Ars Math. Contemp., 14, 2, 319-327 (2018) · Zbl 1393.05092 |
| [24] | Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116 (1956) · Zbl 0070.18403 |
| [25] | Tutte, W. T., The non-biplanar character of the complete 9-graph, Canad. Math. Bull., 6, 319-330 (1963) · Zbl 0113.38803 |
| [26] | Vasak, J. M., The Thickness of the Complete Graphs (1976), ProQuest LLC, University of Illinois at Urbana-Champaign: ProQuest LLC, University of Illinois at Urbana-Champaign Ann Arbor, MI, (thesis Ph.D.) |
| [27] | Yegnanarayanan, V., The pseudoachromatic number of a graph, Southeast Asian Bull. Math., 24, 1, 129-136 (2000) · Zbl 0959.05043 |
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.
