Disproof of a conjecture of Neumann-Lara

Bernardo Llano¹ ; Mika Olsen²

¹Universidad Autónoma Metropolitana - Iztapalapa
²Universidad Autónoma Metropolitana - Cuajimalpa

The electronic journal of combinatorics, Tome 24 (2017) no. 4

Résumé

We disprove the following conjecture due to Víctor Neumann-Lara: for every pair $(r,s)$ of integers such that $r\geq s\geq 2$, there is an infinite set of circulant tournaments $T$ such that the dichromatic number and the cyclic triangle free disconnection of $T$ are equal to $r$ and $s$, respectively. Let $\mathcal{F}_{r,s}$ denote the set of circulant tournaments $T$ with $dc(T)=r$ and $\overrightarrow{\omega }_{3}\left( T\right) =s$. We show that for every integer $s\geq 4$ there exists a lower bound $b(s)$ for the dichromatic number $r$ such that $\mathcal{F}_{r,s}=\emptyset $ for every $r<b(s)$. We construct an infinite set of circulant tournaments $T$ such that $dc(T)=b(s)$ and $\overrightarrow{\omega }_{3}(T)=s$ and give an upper bound $B(s)$ for the dichromatic number $r$ such that for every $r\geq B(s)$ there exists an infinite set $\mathcal{F}_{r,s}$ of circulant tournaments. Some infinite sets $\mathcal{F}_{r,s}$ of circulant tournaments are given for $b(s)<r<B(s)$.

Détail

DOI : 10.37236/5446

Classification : 05C20, 05C15
Mots-clés : circulant tournaments, dichomatic number, acyclic disconnection