Pathwidth and nonrepetitive list coloring (Q504976): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
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 |
Revision as of 02:19, 1 July 2023
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