A note about online nonrepetitive coloring k-trees

2019/09/05 by Balázs Keszegh, Keszegh, Balázs, Xuding Zhu +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory

paper · doi:10.48550/arxiv.1909.02612

Abstract

We prove that it is always possible to color online nonrepetitively any (partial) k-tree (that is, graphs with tree-width at most k) with 4^k colors. This implies that it is always possible to color online nonrepetitively cycles, trees and series-parallel graphs with 16 colors. Our results generalize the respective (offline) nonrepetitive coloring results.

Cited by

• New lower bounds on the non-repetitive chromatic number of some graphs

Related

• Online Edge Coloring of Paths and Trees with a Fixed Number of Colors
• Online Graph Coloring for k-Colorable Graphs
• Tight Bounds for Online Coloring of Basic Graph Classes
• Online Edge Coloring is (Nearly) as Easy as Offline
• Online Edge Coloring: Sharp Thresholds