Pathwidth and nonrepetitive list coloring (Q504976): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / review text | |||
Summary: 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), \textit{F. Fiorenzi} et al. [Discrete Appl. Math. 159, No. 17, 2045--2049 (2011; Zbl 1239.05064)] recently showed that this does not extend to the list version of the problem, that is, for every \(\ell \geq 1\) 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. [loc. cit.]: 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\). | |||
Property / review text: Summary: 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), \textit{F. Fiorenzi} et al. [Discrete Appl. Math. 159, No. 17, 2045--2049 (2011; Zbl 1239.05064)] recently showed that this does not extend to the list version of the problem, that is, for every \(\ell \geq 1\) 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. [loc. cit.]: 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\). / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C15 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6675975 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
graph coloring | |||
Property / zbMATH Keywords: graph coloring / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
nonrepetitive coloring | |||
Property / zbMATH Keywords: nonrepetitive coloring / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pathwidth | |||
Property / zbMATH Keywords: pathwidth / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1601.01886 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive colorings of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive colorings of trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3577833 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive colouring via entropy compression / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Thue choosability of trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3424780 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pattern avoidance on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New approach to nonrepetitive sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive list colourings of paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive vertex colorings of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive Choice Number of Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive colorings of graphs of bounded tree-width / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A constructive proof of the general lovász local lemma / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 08:15, 13 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pathwidth and nonrepetitive list coloring |
scientific article |
Statements
Pathwidth and nonrepetitive list coloring (English)
0 references
18 January 2017
0 references
Summary: 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), \textit{F. Fiorenzi} et al. [Discrete Appl. Math. 159, No. 17, 2045--2049 (2011; Zbl 1239.05064)] recently showed that this does not extend to the list version of the problem, that is, for every \(\ell \geq 1\) 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. [loc. cit.]: 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\).
0 references
graph coloring
0 references
nonrepetitive coloring
0 references
pathwidth
0 references