On the heterochromatic number of circulant digraphs
Hortensia Galeana-Sánchez ; Víctor Neumann-Lara
Discussiones Mathematicae Graph Theory, Tome 24 (2004), p. 73-79 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 Dn,s be the oriented graph such that V(Dn,s) is the set of integers mod 2n+1 and A(Dn,s)=(i,j):j-i∈1,2,...,n∖s..In this paper we prove that hc(Dn,s)≤5 for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].

Publié le : 2004-01-01
EUDML-ID : urn:eudml:doc:270660 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1214,
     author = {Hortensia Galeana-S\'anchez and V\'\i ctor Neumann-Lara},
     title = {On the heterochromatic number of circulant digraphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {24},
     year = {2004},
     pages = {73-79},
     zbl = {1054.05037},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1214}
}

Hortensia Galeana-Sánchez; Víctor Neumann-Lara. On the heterochromatic number of circulant digraphs. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 73-79. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1214/

[000] [1] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973).

[001] [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. | Zbl 0931.05030

[002] [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. | Zbl 0776.05079

[003] [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.

[004] [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. | Zbl 0969.05031

[005] [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. | Zbl 0864.05035

[006] [7] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197-198 (1999) 617-632. | Zbl 0928.05033