KIT | KIT-Bibliothek | Impressum | Datenschutz

The r-dynamic chromatic number is bounded in the strong 2-coloring number

Goetze, Miriam 1; Ueckerdt, Torsten 1
1 Karlsruher Institut für Technologie (KIT)

Abstract:

A proper vertex-coloring of a graph is r-dynamic if the neighbors of each vertex v receive at least min(r, deg(v)) different colors. In this note, we prove that if G has strong 2-coloring number at most k, then G admits an r-dynamic coloring with no more than (k − 1)r + 1 colors. As a consequence, for every class of graphs of bounded expansion, the r-dynamic chromatic number is bounded by a linear function in r. We give a concrete upper bound for graphs of bounded row-treewidth, which includes for example all planar graphs.


Verlagsausgabe §
DOI: 10.5445/IR/1000184773
Veröffentlicht am 11.09.2025
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
KIT-Bibliothek (BIB)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 02.2026
Sprache Englisch
Identifikator ISSN: 0012-365X, 1872-681X
KITopen-ID: 1000184773
Erschienen in Discrete Mathematics
Verlag Elsevier
Band 349
Heft 2
Seiten 114697
Nachgewiesen in Web of Science
OpenAlex
Dimensions
Scopus
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page