Disproof of a Conjecture of Neumann-Lara

Bernardo Llano, Mika Olsen

Abstract


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)$.


Keywords


Circulant tournaments; Dichomatic number; Acyclic disconnection

Full Text:

PDF