Download PDF - Dichromatic number, circulant tournaments and Zykov sums of digraphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Dichromatic number, circulant tournaments and Zykov sums of digraphs

Authors 1

Affiliations

  1. Instituto de Matemáticas, UNAM, Circuito Exterior, C.U., México 04510 D.F., MÉXICO

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

ENG
digraphs, dichromatic number, vertex-critical, Zykov sums, tournaments, circulant, covering numbers in hypergraphs

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2000/20/2
Export to PBN, Opens in new tab
Pages:
197-207
Main language of publication
English
Received
1999-11-10
Accepted
2000-10-30
Published
2000

DOI: 10.7151/dmgt.1119

Exact and natural sciences