Pattern avoidance on graphs (Q878624): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2005.11.071 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1981075828 / rank | |||
Normal rank |
Revision as of 23:23, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pattern avoidance on graphs |
scientific article |
Statements
Pattern avoidance on graphs (English)
0 references
26 April 2007
0 references
The paper studies colorings of graphs avoiding certain patterns on paths. Let \(X\) be a set of variables and let \(p=x_1x_2\dots x_r\) (with \(x_i\in X\)) be a pattern, i.e. any sequence of the variables with repetition allowed. A finite sequence \(s\) is said to match the pattern \(p\), if \(s\) can be divided into non-empty blocks \(s=B_1B_2\dots B_r\), such that \(x_i=x_j\) implies \(B_i=B_j\) for all \(1\leq i,j\leq r\). A coloring of vertices (or edges) of a graph \(G\) is said to be \(p\)-free if no path in \(G\) matches the pattern \(p\). The pattern chromatic number \(\pi_p(G)\) is the minimum number of colors used in a \(p\)-free coloring of \(G\). Extending results of \textit{N. Alon, J. Grytczuk, M. Hałuszczak}, and \textit{O. Riordan} [Random Struct. Algorithms 21, 336--346 (2002; Zbl 1018.05032)], the paper shows that if each variable occurs at least \(m\geq 2\) times in a pattern \(p\), then \(\pi_p(G) \leq c \Delta^{m/(m-1)}\), where \(c\) is an absolute constant and \(\Delta\) is the maximum degree of the graph \(G\). The proof is probabilistic and depends on the Lovász Local Lemma. For certain graph classes stronger results are achieved by providing explicit \(p\)-free colorings. In particular, for some patterns \(p\), the pattern chromatic number has an absolute upper bound for all trees.
0 references
nonrepetitive graph coloring
0 references
pattern chromatic number
0 references
avoidable pattern
0 references
Lovász Local Lemma
0 references