Pathwidth and nonrepetitive list coloring

zbMATH Open1353.05048arXiv1601.01886MaRDI 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)

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$.

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

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

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

zbMATH Keywords

graph coloringpathwidthnonrepetitive coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

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

Cited In (10)

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

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)