Dynamic coloring parameters for graphs with given genus

DOI10.1016/J.DAM.2017.09.013MaRDI QIDQ1682887zbMATH OpenOpenAlexFDO

Authors Sarah Loeb, Thomas Mahoney, Benjamin Reiniger, Jennifer I. Wise

Publication date 6 December 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03983

zbMATH Keywords

\(r\)-dynamic coloring\(r\)-dynamic paintabilitygraph genus

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: A proper vertex coloring of a graph $G$ is $r$-dynamic if for each $vinV(G)$, at least $minr,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 $gleq2$ and $r$-dynamically $((r+1)(2g+2)+3)$-colorable when $ggeq3$. Furthermore, each of these upper bounds for $r$-dynamic $k$-colorability also holds for $r$-dynamic $k$-choosability and for $r$-dynamic $k$-paintability. We develop a method to prove that certain configurations are reducible for each of the corresponding $r$-dynamic parameters.

Recommendations

• On dynamic coloring for planar graphs and graphs of higher genus
• Optimal \(r\)-dynamic coloring of sparse graphs
• 3-dynamic coloring of planar triangulations
• On \(r\)-dynamic coloring of graphs
• List \(r\)-dynamic coloring of sparse graphs

Cites work

• A survey on the distance-colouring of graphs
• Brooks' theorem via the Alon-Tarsi theorem
• Dynamic coloring and list dynamic coloring of planar graphs
• Every planar graph is 5-choosable
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 125461 (Why is no real title available?)
• Largest planar graphs of diameter two and fixed maximum degree
• List colourings of planar graphs
• List Dynamic Coloring of Sparse Graphs
• List-coloring the square of a subcubic graph
• Mr. Paint and Mrs. Correct
• On \(r\)-dynamic coloring of graphs
• On \(r\)-dynamic coloring of grids
• On r-hued coloring of K₄-minor free graphs
• On dynamic coloring for planar graphs and graphs of higher genus
• On the list dynamic coloring of graphs
• On the total coloring of planar graphs.
• On-line list colouring of graphs

Cited in

(24)

• List 3-dynamic coloring of graphs with small maximum average degree
• List r-dynamic coloring of graphs with small maximum average degree
• Upper bounds of r-hued colorings of planar graphs
• 3-dynamic coloring of planar triangulations
• On \(r\)-hued list coloring of \(K_4 ( 7 )\)-minor free graphs
• On the \(r\)-dynamic coloring of subdivision-edge coronas of a path
• On the \(r\)-dynamic coloring of the direct product of a path with either a complete graph or a wheel graph
• On the r-dynamic coloring of the direct product of a path with either a path or a cycle
• Graph \(r\)-hued colorings -- a survey
• Game connectivity of graphs
• On list 3-dynamic coloring of near-triangulations
• \(r\)-hued \((r+1)\)-coloring of planar graphs with girth at least 8 for \(r\geq 9\)
• List \(r\)-dynamic coloring of sparse graphs
• Dynamic list coloring of 1-planar graphs
• Brooks-type theorem for \(r\)-hued coloring of graphs
• On \(r\)-dynamic coloring of graphs
• On dynamic coloring for planar graphs and graphs of higher genus
• The structure and the list 3-dynamic coloring of outer-1-planar graphs
• The $r$-dynamic edge coloring of a closed helm graph
• List 3-dynamic colorings of planar graphs
• Upper bound of the list r-hued chromatic number
• A note on the r-hued coloring of planar graphs
• The r-dynamic chromatic number is bounded in the strong 2-coloring number
• Improved bounds of r-hued colorings of planar graphs

This page was built for publication: Dynamic coloring parameters for graphs with given genus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1682887)