On Some Interesting Ternary Formulas - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2017

On Some Interesting Ternary Formulas

Pascal Ochem
Algorithmes, Graphes et Combinatoire
CV
Matthieu Rosenfeld
Modèles de calcul, Complexité, Combinatoire

Abstract

We show that, up to renaming of the letters, the only infinite ternary words avoiding the formula ABCAB.ABCBA.ACB.BAC (resp. ABCA.BCAB.BCB.CBA) have the same set of recurrent factors as the fixed point of $0->012,1->02,2->1$ Also, we show that the formula ABAC.BACA.ABCA is 2-avoidable. Finally, we show that the pattern ABACADABCA is unavoidable for the class of $C_4$-minor-free graphs with maximum degree 3. This disproves a conjecture of Grytczuk.

Domains

Discrete Mathematics [cs.DM] Combinatorics [math.CO]

Alexandre Pinlou  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02078252

Submitted on : Monday, March 25, 2019-10:51:35 AM

Last modification on : Thursday, March 14, 2024-3:12:43 AM

Consult the full text

Dates and versions

lirmm-02078252 , version 1 (25-03-2019)

Identifiers

Cite

Pascal Ochem, Matthieu Rosenfeld. On Some Interesting Ternary Formulas. WORDS 2017 - 11th International Conference on Combinatorics on Words, Sep 2017, Montreal, Canada. pp.30-35, ⟨10.1007/978-3-319-66396-8_4⟩. ⟨lirmm-02078252⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

ENS-LYON CNRS INRIA UNIV-LYON1 ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER UDL ANR
67 View
0 Download

Altmetric

Share

More