A note about online nonrepetitive coloring k-trees

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

Authors: 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

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

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 (3)

• Online edge coloring via tree recurrences and correlation decay
• On the long-repetition-free 2-colorability of trees
• 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)