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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1119,
author = {V\'\i ctor Neumann-Lara},
title = {Dichromatic number, circulant tournaments and Zykov sums of digraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {20},
year = {2000},
pages = {197-207},
zbl = {0984.05043},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1119}
}
Víctor Neumann-Lara. Dichromatic number, circulant tournaments and Zykov sums of digraphs. Discussiones Mathematicae Graph Theory, Tome 20 (2000) pp. 197-207. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1119/
[000] [1] C. Berge, Graphs and Hypergraphs (Amsterdam, North Holland Publ. Co., 1973). | Zbl 0254.05101
[001] [2] J.A. Bondy, U.S.R Murty, Graph Theory with Applications (American Elsevier Pub. Co., 1976). | Zbl 1226.05083
[002] [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.
[003] [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. | Zbl 0743.05047
[004] [5] P. Erdős and V. Neumann-Lara, On the dichromatic number of a graph, in preparation.
[005] [6] D.C. Fisher, Fractional Colorings with large denominators, J. Graph Theory, 20 (1995) 403-409, doi: 10.1002/jgt.3190200403. | Zbl 0837.05054
[006] [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. | Zbl 0282.05114
[007] [8] A.J.W. Hilton, R. Rado, and S.H. Scott, Multicolouring graphs and hypergraphs, Nanta Mathematica 9 (1975) 152-155. | Zbl 0395.05036
[008] [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. | Zbl 0525.05027
[009] [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. | Zbl 0506.05031
[010] [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.
[011] [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. | Zbl 0829.05028
[012] [13] V. Neumann-Lara, Vertex-critical 4-dichromatic circulant tournaments, Discrete Math. 170 (1997) 289- 291, doi: 10.1016/S0012-365X(96)00128-8. | Zbl 0876.05039
[013] [14] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197/198 (1999) 617-632. | Zbl 0928.05033
[014] [15] V. Neumann-Lara and J. Urrutia, Vertex-critical r-dichromatic tournaments, Discrete Math. 40 (1984) 83-87. | Zbl 0532.05031
[015] [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. | Zbl 0613.05023
[016] [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. | Zbl 0293.05115