# 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
Full Text:
##### References:
  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  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  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  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  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)  Heawood, P. J., Map colour theorem, Q. J. Math., 24, 332-338, (1890), MR 0030735 (11,43d) · JFM 22.0562.02  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  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  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  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  Kang, Ross; Müller, Tobias; West, Douglas B., On $$r$$-dynamic coloring of grids, Discrete Appl. Math., 186, 286-290, (2015) · Zbl 1311.05066  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  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  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  Mahoney, Thomas, Online Choosability of Graphs, (2015), ProQuest LLC, Univ. Illinois, Urbana-Champaign, (Ph.D. thesis)  Montgomery, Bruce, Dynamic Coloring of Graphs, 52, (2001), ProQuest LLC, Ann Arbor, MI, West Virginia University. MR 2702379  Schauz, Uwe, Mr. paint and mrs. correct, Electron. J. Combin., 16, 1, (2009), Research Paper 77, 18. MR 2515754 (2010i:91064) · Zbl 1186.05085  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  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  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)  Voigt, Margit, List colourings of planar graphs, Discrete Math., 120, 1-3, 215-219, (1993), MR 1235909 (94d:05061) · Zbl 0790.05030  Gerd Wegner, Graphs with given diameter and a coloring problem, Tech. report, University of Dortmund, 1977.  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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.6349121,"math_prob":0.94526106,"size":5773,"snap":"2021-04-2021-17","text_gpt3_token_len":2005,"char_repetition_ratio":0.14803259,"word_repetition_ratio":0.021531101,"special_character_ratio":0.41468906,"punctuation_ratio":0.2922029,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97754544,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-01-16T18:59:13Z\",\"WARC-Record-ID\":\"<urn:uuid:c7001660-685b-4b9e-a7f4-51ed68c61705>\",\"Content-Length\":\"55805\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:293c0e3c-4273-42a3-8635-0743e0355fcf>\",\"WARC-Concurrent-To\":\"<urn:uuid:4d108f24-9cec-4db3-8a80-ef2177f902c5>\",\"WARC-IP-Address\":\"141.66.194.3\",\"WARC-Target-URI\":\"https://www.zbmath.org/?q=ai%3Areiniger.benjamin-m+ai%3Amahoney.thomas\",\"WARC-Payload-Digest\":\"sha1:2DPQ6TAXFMJSTDUK572NOYNNGL5GI7IE\",\"WARC-Block-Digest\":\"sha1:7HCVIFKN4PY2Q5IBKEO7FV4EVTSO2B6S\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-04/CC-MAIN-2021-04_segments_1610703506832.21_warc_CC-MAIN-20210116165621-20210116195621-00292.warc.gz\"}"}