Dichromatic number, circulant tournaments and Zykov sums of digraphs

Víctor Neumann-Lara

Discussiones Mathematicae Graph Theory (2000)

  • Volume: 20, Issue: 2, page 197-207
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Víctor Neumann-Lara. "Dichromatic number, circulant tournaments and Zykov sums of digraphs." Discussiones Mathematicae Graph Theory 20.2 (2000): 197-207. <http://eudml.org/doc/270756>.

@article{VíctorNeumann2000,
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.},
author = {Víctor Neumann-Lara},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {digraphs; dichromatic number; vertex-critical; Zykov sums; tournaments; circulant; covering numbers in hypergraphs; digraph; Zykov sum; circulant tournaments},
language = {eng},
number = {2},
pages = {197-207},
title = {Dichromatic number, circulant tournaments and Zykov sums of digraphs},
url = {http://eudml.org/doc/270756},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Víctor Neumann-Lara
TI - Dichromatic number, circulant tournaments and Zykov sums of digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 2
SP - 197
EP - 207
AB - 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.
LA - eng
KW - digraphs; dichromatic number; vertex-critical; Zykov sums; tournaments; circulant; covering numbers in hypergraphs; digraph; Zykov sum; circulant tournaments
UR - http://eudml.org/doc/270756
ER -

References

top
  1. [1] C. Berge, Graphs and Hypergraphs (Amsterdam, North Holland Publ. Co., 1973). Zbl0254.05101
  2. [2] J.A. Bondy, U.S.R Murty, Graph Theory with Applications (American Elsevier Pub. Co., 1976). Zbl1226.05083
  3. [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. [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. Zbl0743.05047
  5. [5] P. Erdős and V. Neumann-Lara, On the dichromatic number of a graph, in preparation. 
  6. [6] D.C. Fisher, Fractional Colorings with large denominators, J. Graph Theory, 20 (1995) 403-409, doi: 10.1002/jgt.3190200403. Zbl0837.05054
  7. [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. Zbl0282.05114
  8. [8] A.J.W. Hilton, R. Rado, and S.H. Scott, Multicolouring graphs and hypergraphs, Nanta Mathematica 9 (1975) 152-155. Zbl0395.05036
  9. [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. Zbl0525.05027
  10. [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. Zbl0506.05031
  11. [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. [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. Zbl0829.05028
  13. [13] V. Neumann-Lara, Vertex-critical 4-dichromatic circulant tournaments, Discrete Math. 170 (1997) 289- 291, doi: 10.1016/S0012-365X(96)00128-8. Zbl0876.05039
  14. [14] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197/198 (1999) 617-632. Zbl0928.05033
  15. [15] V. Neumann-Lara and J. Urrutia, Vertex-critical r-dichromatic tournaments, Discrete Math. 40 (1984) 83-87. Zbl0532.05031
  16. [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. Zbl0613.05023
  17. [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. Zbl0293.05115

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.