Name
Abstract | ||
|---|---|---|
We obtain the following results about the avoidance of ternary formulas. Up to renaming of the letters, the only infinite ternary words avoiding the formula ABCAB.ABCBA.ACB.BAC (resp. ABCA.BCAB.BCB.CBA) are the ones that have the same set of recurrent factors as the fixed point of 0 bar right arrow 012, 1 bar right arrow 02, 2 bar right arrow 1. The formula ABAC.BACA.ABCA is avoided by polynomially many binary words (w.r.t. to their lengths) and there exist arbitrarily many infinite binary words with different sets of recurrent factors that avoid it. If every variable of a ternary formula appears at least twice in the same fragment, then the formula is 3-avoidable. The pattern ABACADABCA is unavoidable for the class of C-4-minorfree graphs with maximum degree 3. This disproves a conjecture of Grytczuk. The formula ABCA.ACBA, or equivalently the palindromic pattern ABCADACBA, has avoidability index 4. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-66396-8_4 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Conference | 26.0 | 1.0 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
2 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pascal Ochem | 1 | 258 | 36.91 |
| Matthieu Rosenfeld | 2 | 0 | 0.34 |