PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 1 | 73-79
Tytuł artykułu

On the heterochromatic number of circulant digraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
The heterochromatic number hc(D) of a digraph D, is the minimum integer k such that for every partition of V(D) into k classes, there is a cyclic triangle whose three vertices belong to different classes.
For any two integers s and n with 1 ≤ s ≤ n, let $D_{n,s}$ be the oriented graph such that $V(D_{n,s})$ is the set of integers mod 2n+1 and $A(D_{n,s}) = {(i,j) : j-i ∈ {1,2,...,n}∖{s}}..
In this paper we prove that $hc(D_{n,s}) ≤ 5$ for n ≥ 7. The bound is tight since equality holds when s ∈ {n,[(2n+1)/3]}.
Wydawca
Rocznik
Tom
24
Numer
1
Strony
73-79
Opis fizyczny
Daty
wydano
2004
otrzymano
2001-06-29
poprawiono
2003-05-13
Twórcy
  • Instituto de Matemáticas, UNAM, Universidad Nacional Autónoma de México, Ciudad Universitaria, 04510, México, D.F., MÉXICO
  • Instituto de Matemáticas, UNAM, Universidad Nacional Autónoma de México, Ciudad Universitaria, 04510, México, D.F., MÉXICO
Bibliografia
  • [1] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973).
  • [2] B. Abrego, J.L. Arocha, S. Fernández Merchant and V. Neumann-Lara, Tightness problems in the plane, Discrete Math. 194 (1999) 1-11, doi: 10.1016/S0012-365X(98)00031-4.
  • [3] J.L. Arocha, J. Bracho and V. Neumann-Lara, On the minimum size of tight hypergraphs, J. Graph Theory 16 (1992) 319-326, doi: 10.1002/jgt.3190160405.
  • [4] P. Erdős, M. Simonovits and V.T. Sós, Anti-Ramsey Theorems (in: Infinite and Finite Sets, Keszthely, Hungary, 1973), Colloquia Mathematica Societatis János Bolyai 10 633-643.
  • [5] H. Galeana-Sánchez and V. Neumann-Lara, A class of tight circulant tournaments, Discuss. Math. Graph Theory 20 (2000) 109-128, doi: 10.7151/dmgt.1111.
  • [6] Y. Manoussakis, M. Spyratos, Zs. Tuza, M. Voigt, Minimal colorings for properly colored subgraphs, Graphs and Combinatorics 12 (1996) 345-360, doi: 10.1007/BF01858468.
  • [7] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197-198 (1999) 617-632.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1214
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ć.