×

zbMATH — the first resource for mathematics

Dynamic coloring parameters for graphs with given genus. (English) Zbl 1375.05098
Summary: A proper vertex coloring of a graph \(G\) is \(r\)-dynamic if for each \(v\in V(G)\), at least \(\min\{r,d(v)\}\) colors appear in \(N_G(v)\). In this paper we investigate \(r\)-dynamic versions of coloring, list coloring, and paintability. We prove that planar and toroidal graphs are 3-dynamically 10-colorable, and this bound is sharp for toroidal graphs. We also give bounds on the minimum number of colors needed for any \(r\) in terms of the genus of the graph: for sufficiently large \(r\), every graph with genus \(g\) is \(r\)-dynamically \(((r+1)(g+5)+3)\)-colorable when \(g\leq 2\) and \(r\)-dynamically \(((r+1)(2g+2)+3)\)-colorable when \(g\geq 3\). Furthermore, each of these upper bounds for \(r\)-dynamic \(k\)-colorability also holds for \(r\)-dynamic \(k\)-choosability and for \(r\)-dynamic \(k\)-paintability.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Akbari, S.; Ghanbari, M.; Jahanbekam, S., On the List dynamic coloring of graphs, Discrete Appl. Math., 157, 14, 3005-3007, (2009), MR 2553387 (2010i:05289) · Zbl 1211.05038
[2] Borodin, O. V., On the total coloring of planar graphs, J. Reine Angew. Math., 394, 180-185, (1989), MR 977440 (89m:05049) · Zbl 0653.05029
[3] Chen, Ye; Fan, Suohai; Lai, Hong-Jian; Song, Huimin; Sun, Lei, On dynamic coloring for planar graphs and graphs of higher genus, Discrete Appl. Math., 160, 7-8, 1064-1071, (2012), MR 2901126 · Zbl 1243.05079
[4] Cranston, Daniel W.; Kim, Seog-Jin, List-coloring the square of a subcubic graph, J. Graph Theory, 57, 1, 65-87, (2008), MR 2370185 (2008k:05072) · Zbl 1172.05023
[5] Erdős, Paul; Rubin, Arthur L.; Taylor, Herbert, Choosability in graphs, (Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., vol. XXVI, (1980), Utilitas Math. Winnipeg, Man.), 125-157, MR 593902 (82f:05038)
[6] Heawood, P. J., Map colour theorem, Q. J. Math., 24, 332-338, (1890), MR 0030735 (11,43d) · JFM 22.0562.02
[7] Hell, P.; Seyffarth, K., Largest planar graphs of diameter two and fixed maximum degree, Discrete Math., 111, 1-3, 313-322, (1993), Graph theory and combinatorics (Marseille-Luminy, 1990). MR 1210107 (93j:05086) · Zbl 0837.05074
[8] Hladký, Jan; Král’, Daniel; Schauz, Uwe, Brooks’ theorem via the Alon-tarsi theorem, Discrete Math., 310, 23, 3426-3428, (2010), MR 2721105 (2012a:05115) · Zbl 1222.05061
[9] Ivančo, Jaroslav, The weight of a graph, (Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), Ann. Discrete Math., vol. 51, (1992), North-Holland Amsterdam), 113-116, MR 1206252 (94h:05044) · Zbl 0773.05066
[10] Jahanbekam, Sogol; Kim, Jaehoon; Suil, O.; West, Douglas B., On \(r\)-dynamic coloring of graphs, Discrete Appl. Math., 206, 65-72, (2016) · Zbl 1335.05065
[11] Kang, Ross; Müller, Tobias; West, Douglas B., On \(r\)-dynamic coloring of grids, Discrete Appl. Math., 186, 286-290, (2015) · Zbl 1311.05066
[12] Kim, Seog-Jin; Lee, Sang June; Park, Won-Jin, Dynamic coloring and List dynamic coloring of planar graphs, Discrete Appl. Math., 161, 13-14, 2207-2212, (2013), MR 3057028 · Zbl 1287.05046
[13] Kim, Seog-Jin; Park, Won-Jin, List dynamic coloring of sparse graphs, (Combinatorial Optimization and Applications, Lecture Notes in Comput. Sci., vol. 6831, (2011), Springer Heidelberg), 156-162, MR 2878434 · Zbl 1342.05043
[14] Kramer, Florica; Kramer, Horst, A survey on the distance-colouring of graphs, Discrete Math., 308, 2-3, 422-426, (2008), MR 2378044 (2008i:05065) · Zbl 1130.05026
[15] Mahoney, Thomas, Online Choosability of Graphs, (2015), ProQuest LLC, Univ. Illinois, Urbana-Champaign, (Ph.D. thesis)
[16] Montgomery, Bruce, Dynamic Coloring of Graphs, 52, (2001), ProQuest LLC, Ann Arbor, MI, West Virginia University. MR 2702379
[17] Schauz, Uwe, Mr. paint and mrs. correct, Electron. J. Combin., 16, 1, (2009), Research Paper 77, 18. MR 2515754 (2010i:91064) · Zbl 1186.05085
[18] Song, Huimin; Fan, Suohai; Chen, Ye; Sun, Lei; Lai, Hong-Jian, On \(r\)-hued coloring of \(K_4\)-minor free graphs, Discrete Math., 315, 47-52, (2014), MR 3130354 · Zbl 1278.05109
[19] Thomassen, Carsten, Every planar graph is \(5\)-choosable, J. Combin. Theory Ser. B, 62, 1, 180-181, (1994), MR 1290638 (95f:05045) · Zbl 0805.05023
[20] Vizing, V. G., Coloring the vertices of a graph in prescribed colors, Diskret. Anal., 29, (1976), Metody Diskret. Anal. v Teorii Kodov i Shem, 3-10, 101. MR 0498216 (58 #16371)
[21] Voigt, Margit, List colourings of planar graphs, Discrete Math., 120, 1-3, 215-219, (1993), MR 1235909 (94d:05061) · Zbl 0790.05030
[22] Gerd Wegner, Graphs with given diameter and a coloring problem, Tech. report, University of Dortmund, 1977.
[23] Zhu, Xuding, On-line List colouring of graphs, Electron. J. Combin., 16, 1, (2009), Research Paper 127, 16. MR 2558264 (2011a:05123) · Zbl 1186.05061
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.