Pattern avoidance on graphs (Q878624): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Jarosław Grytczuk / rank | |||
Property / author | |||
Property / author: Jarosław Grytczuk / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
Property / cites work | |||
Property / cites work: Q4330617 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonrepetitive colorings of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2784326 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Growth problems for avoidable words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Avoidable patterns in strings of symbols / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4714446 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Open Problems in Pattern Avoidance / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4412125 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On nonrepetitive sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Characterization of the Morse Minimal Set / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5461543 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Non-repetitive colorings of infinite sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Square-free and cube-free colorings of the ordinals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3659988 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multiplicative properties of the Thue-Morse sequence / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph colouring and the probabilistic method / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5730165 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5646912 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Substitution dynamical systems - spectral analysis / rank | |||
Normal rank |
Latest revision as of 18:14, 25 June 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