PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2000 | 20 | 2 | 197-207
Tytuł artykułu

Dichromatic number, circulant tournaments and Zykov sums of digraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
20
Numer
2
Strony
197-207
Opis fizyczny
Daty
wydano
2000
otrzymano
1999-11-10
poprawiono
2000-10-30
Twórcy
  • Instituto de Matemáticas, UNAM, Circuito Exterior, C.U., México 04510 D.F., MÉXICO
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1119
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.