The Dichromatic Number of Infinite Families of Circulant Tournaments

Javier, Nahid ; Llano, Bernardo

Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 221-238

Résumé

The dichromatic number dc(D) of a digraph D is defined to be the minimum number of colors such that the vertices of D can be colored in such a way that every chromatic class induces an acyclic subdigraph in D. The cyclic circulant tournament is denoted by T= C⃗_2n+1(1,2,…,n), where V (T) = ℤ_2n+1 and for every jump j ∈1, 2, . . ., n there exist the arcs (a, a + j) for every a ∈ℤ_2n+1. Consider the circulant tournament C⃗_2n+1 〈k〉 obtained from the cyclic tournament by reversing one of its jumps, that is, C⃗_2n+1 〈k〉 has the same arc set as C⃗_2n+1 (1,2,…,n) except for j = k in which case, the arcs are (a, a − k) for every a ∈ℤ_2n+1. In this paper, we prove that dc (C⃗_2n+1 〈k〉 ) ∈2,3,4 for every k ∈1, 2, . . ., n. Moreover, we classify which circulant tournaments C⃗_2n+1 〈k〉 are vertex-critical r-dichromatic for every k ∈1, 2, . . ., n and r ∈2, 3, 4. Some previous results by Neumann-Lara are generalized.

Détail

Keywords: tournament, dichromatic number, vertex-critical r -dichromatic tournament