A note about online nonrepetitive coloring k-trees

DOI10.1016/J.DAM.2020.04.026zbMATH1447.05085OpenAlexW3034604849MaRDI QIDQ2197409FDOQ2197409

Authors Balázs Keszegh, Xuding Zhu

Publication date 31 August 2020

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

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)

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.

Recommendations

• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive colorings of graphs
• Nonrepetitive edge-colorings of trees
• Pathwidth and nonrepetitive list coloring
• Notes on nonrepetitive graph colouring

Cites work

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

Cited in

(3)

• Extensions and reductions of squarefree words
• Online edge coloring via tree recurrences and correlation decay
• On the long-repetition-free 2-colorability of trees

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)