Yes, (2K2, K4)-free graphs are recolorable

Henry Echeverr\'ia; Owen Henderschedt

Matemática y estadísticaCombinatoria y matemática discreta

Yes, $(2 K_{2}, K_{4})$ -free graphs are recolorable

Henry Echeverr\'ia, Owen Henderschedt

Preprint

En palabras de los autores

We prove that every $(2 K_{2}, K_{4})$ -free graph is recolorable. Equivalently, for every such graph $G$ and every $ℓ \geq χ (G) + 1$ , the reconfiguration graph of proper $ℓ$ -colorings of $G$ , in which two colorings are adjacent if they differ on exactly one vertex, is connected. This resolves the final remaining open case in the classification of recolorable $(F_{1}, F_{2})$ -free graphs when $F_{1}$ and $F_{2}$ have at most four vertices.

Resultado principalEl resumen no menciona limitaciones.

Leer el paper PDF

Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.

Yes, (2K2​,K4​)-free graphs are recolorable

En palabras de los autores

Más de Combinatoria y matemática discreta ese día

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Boolean threshold functions, neuron capacity, and memory retrieval

The Marcus-Minc Transform Inequality

The coarse Erd\H{o}s-P\'{o}sa theorem

A Combinatorial Proof of Hilton's Conjecture and Beyond

Yes, $(2 K_{2}, K_{4})$ -free graphs are recolorable