Pathwidth and nonrepetitive list coloring

zbMATH Open1353.05048MaRDI QIDQ504976FDOQ504976

Authors Adam Gągol, Gwenaël Joret, Jakub Kozik, Piotr Micek 

Publication date 18 January 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph coloringpathwidthnonrepetitive coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A vertex coloring of a graph is nonrepetitive if there is no path in the graph whose first half receives the same sequence of colors as the second half. While every tree can be nonrepetitively colored with a bounded number of colors (4 colors is enough), Fiorenzi, Ochem, Ossona de Mendez, and Zhu recently showed that this does not extend to the list version of the problem, that is, for every $ellgeq1$ there is a tree that is not nonrepetitively $ell$-choosable. In this paper we prove the following positive result, which complements the result of Fiorenzi et al.: There exists a function $f$ such that every tree of pathwidth $k$ is nonrepetitively $f(k)$-choosable. We also show that such a property is specific to trees by constructing a family of pathwidth-2 graphs that are not nonrepetitively $ell$-choosable for any fixed $ell$.

Recommendations

• Nonrepetitive choice number of trees
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive colorings of trees
• Nonrepetitive list colourings of paths
• Thue choosability of trees

Cites work

• scientific article; zbMATH DE number 5130733 (Why is no real title available?)
• A constructive proof of the general Lovász local lemma
• Graph theory
• New approach to nonrepetitive sequences
• Nonrepetitive choice number of trees
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive colorings of trees
• Nonrepetitive colouring via entropy compression
• Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
• Nonrepetitive list colourings of paths
• Nonrepetitive vertex colorings of graphs
• Pattern avoidance on graphs
• Thue choosability of trees

Cited in

(10)

• New bounds for facial nonrepetitive colouring
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive list colourings of paths
• A note about online nonrepetitive coloring \(k\)-trees
• The list chromatic number of graphs with small clique number
• Nonrepetitive choice number of trees
• Every plane graph is facially-non-repetitively \(C\)-choosable
• Anagram-free graph colouring
• \((2+\epsilon )\)-nonrepetitive list colouring of paths
• Avoiding squares over words with lists of size three amongst four symbols

This page was built for publication: Pathwidth and nonrepetitive list coloring

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