Geodesic
The Dichromatic Number of Infinite Families of Circulant Tournaments
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 221-238.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: tournament, dichromatic number, vertex-critical r -dichromatic tournament 
@article{DMGT_2017_37_1_a15,
     author = {Javier, Nahid and Llano, Bernardo},
     title = {The {Dichromatic} {Number} of {Infinite} {Families} of {Circulant} {Tournaments}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {221--238},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a15/}
}
TY  - JOUR
AU  - Javier, Nahid
AU  - Llano, Bernardo
TI  - The Dichromatic Number of Infinite Families of Circulant Tournaments
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 221
EP  - 238
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a15/
LA  - en
ID  - DMGT_2017_37_1_a15
ER  - 
%0 Journal Article
%A Javier, Nahid
%A Llano, Bernardo
%T The Dichromatic Number of Infinite Families of Circulant Tournaments
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 221-238
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a15/
%G en
%F DMGT_2017_37_1_a15
Javier, Nahid; Llano, Bernardo. The Dichromatic Number of Infinite Families of Circulant Tournaments. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 221-238. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a15/

[1] G. Araujo-Pardo and M. Olsen, A conjecture of Neumann-Lara on infinite families of r-dichromatic circulant tournaments, Discrete Math. 310 (2010) 489–492. doi:10.1016/j.disc.2009.03.028

[2] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications, Second Edition (Springer Monographs in Mathematics, Springer-Verlag London, London, 2009).

[3] P. Erdős, Problems and results in number theory and graph theory, Proceedings of the Ninth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1979), Congr. Numer. XXVII (1979) 3–21.

[4] P. Erdős, J. Gimbel and D. Kratsch, Some extremal results in cochromatic and dichromatic theory, J. Graph Theory 15 (1991) 579–585. doi:10.1002/jgt.3190150604

[5] A. Harutyunyan, Brooks-type results for coloring of digraphs, PhD thesis supervised by B. Mohar (Simon Fraser University, 2011). http://www.math.univ-toulouse.fr/~aharutyu/thes-short.pdf

[6] H. Jacob and H. Meyniel, Extensions of Turan’s and Brooks theorem and new notions of stability and colouring in digraphs, Ann. Discrete Math. 17 (1983) 365–370.

[7] B. Llano and M. Olsen, On a conjecture of Víctor Neumann-Lara, Electron. Notes Discrete Math. 30 (2008) 207–212. doi:10.1016/j.endm.2008.01.036

[8] B. McKay, Combinatorial Data, published online. http://cs.anu.edu.au/~bdm/data

[9] V. Neumann-Lara, The dichromatic number of a digraph, J. Combin. Theory, Ser. B 33 (1982) 265–270. doi:10.1016/0095-8956(82)90046-6

[10] V. Neumann-Lara, The 3 and 4 -dichromatic tournaments of minimum order, Discrete Math. 135 (1994) 233–243. doi:10.1016/0012-365X(93)E0113-I

[11] V. Neumann-Lara, Vertex critical 4 -dichromatric circulant tournaments, Discrete Math. 170 (1997) 289–291. doi:10.1016/S0012-365X(96)00128-8

[12] V. Neumann-Lara, Dichromatic number, circulant tournaments and Zykov sums of digraphs, Discuss. Math. Graph Theory 20 (2000) 197–207. doi:10.7151/dmgt.1119

[13] V. Neumann-Lara and J. Urrutia, Vertex critical r-dichromatric tournaments, Discrete Math. 49 (1984) 83–87. doi:10.1016/0012-365X(84)90154-7