Geodesic
Dichromatic number, circulant tournaments and Zykov sums of digraphs
Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 2, pp. 197-207.

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

The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic circulant tournaments for every k ≥ 3, k ≠ 7.
Keywords: digraphs, dichromatic number, vertex-critical, Zykov sums, tournaments, circulant, covering numbers in hypergraphs 
@article{DMGT_2000_20_2_a3,
     author = {Neumann-Lara, V{\'\i}ctor},
     title = {Dichromatic number, circulant tournaments and {Zykov} sums of digraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {197--207},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2000},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2000_20_2_a3/}
}
TY  - JOUR
AU  - Neumann-Lara, Víctor
TI  - Dichromatic number, circulant tournaments and Zykov sums of digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2000
SP  - 197
EP  - 207
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2000_20_2_a3/
LA  - en
ID  - DMGT_2000_20_2_a3
ER  - 
%0 Journal Article
%A Neumann-Lara, Víctor
%T Dichromatic number, circulant tournaments and Zykov sums of digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2000
%P 197-207
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2000_20_2_a3/
%G en
%F DMGT_2000_20_2_a3
Neumann-Lara, Víctor. Dichromatic number, circulant tournaments and Zykov sums of digraphs. Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 2, pp. 197-207. http://geodesic.mathdoc.fr/item/DMGT_2000_20_2_a3/

[1] C. Berge, Graphs and Hypergraphs (Amsterdam, North Holland Publ. Co., 1973).

[2] J.A. Bondy, U.S.R Murty, Graph Theory with Applications (American Elsevier Pub. Co., 1976).

[3] P. Erdős, Problems and results in number theory and graph theory, in: Proc. Ninth Manitoba Conf. Numer. Math. and Computing (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] P. Erdős and V. Neumann-Lara, On the dichromatic number of a graph, in preparation.

[6] D.C. Fisher, Fractional Colorings with large denominators, J. Graph Theory, 20 (1995) 403-409, doi: 10.1002/jgt.3190200403.

[7] D. Geller and S. Stahl, The chromatic number and other parameters of the lexicographical product, J. Combin. Theory (B) 19 (1975) 87-95, doi: 10.1016/0095-8956(75)90076-3.

[8] A.J.W. Hilton, R. Rado, and S.H. Scott, Multicolouring graphs and hypergraphs, Nanta Mathematica 9 (1975) 152-155.

[9] H. Jacob and H. Meyniel, Extension of Turan's and Brooks theorems and new notions of stability and colorings in digraphs, Ann. Discrete Math. 17 (1983) 365-370.

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

[11] V. Neumann-Lara, The generalized dichromatic number of a digraph, in: Colloquia Math. Soc. Jânos Bolyai, Finite and Infinite Sets 37 (1981) 601-606.

[12] 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.

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

[14] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197/198 (1999) 617-632.

[15] V. Neumann-Lara and J. Urrutia, Vertex-critical r-dichromatic tournaments, Discrete Math. 40 (1984) 83-87.

[16] V. Neumann-Lara and J. Urrutia, Uniquely colourable r-dichromatic tournaments, Discrete Math. 62 (1986) 65-70, doi: 10.1016/0012-365X(86)90042-7.

[17] S. Stahl, n-tuple colourings and associated graphs, J. Combin. Theory (B) 20 (1976) 185-203, doi: 10.1016/0095-8956(76)90010-1.