PDF

Discussiones Mathematicae Graph Theory 20(2) (2000) 197-207
DOI: https://doi.org/10.7151/dmgt.1119

DICHROMATIC NUMBER, CIRCULANT TOURNAMENTS AND ZYKOV SUMS OF DIGRAPHS

Víctor Neumann-Lara

Instituto de Matemáticas, UNAM
Circuito Exterior, C.U.
México 04510 D.F., MÉXICO
e-mail: neumann@matem.unam.mx

Abstract

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.

2000 Mathematics Subject Classification: 05C20, 05C15, 05C65.

References

[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 tour- naments, 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.

Received 10 November 1999
Revised 30 October 2000