A note about online nonrepetitive coloring k-trees

DOI10.1016/J.DAM.2020.04.026zbMATH Open1447.05085arXiv1909.02612OpenAlexW3034604849MaRDI QIDQ2197409FDOQ2197409

Balázs Keszegh, Xuding Zhu

Publication date: 31 August 2020

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

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.

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

zbMATH Keywords

online coloringnonrepetitive coloringbounded tree-width

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Thue choosability of trees
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs -- a survey
• Online Conflict‐Free Coloring for Intervals
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive Choice Number of Trees
• Planar graphs have bounded nonrepetitive chromatic number
• Online version of the theorem of Thue

Cited In (2)

• Online edge coloring via tree recurrences and correlation decay
• Extensions and reductions of squarefree words

This page was built for publication: A note about online nonrepetitive coloring \(k\)-trees

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