Discussiones Mathematicae Graph Theory 24(1) (2004) 73-79
DOI: https://doi.org/10.7151/dmgt.1214
ON THE HETEROCHROMATIC NUMBER
OF CIRCULANT DIGRAPHS
Hortensia Galeana-Sánchez and Víctor Neumann-Lara
Instituto de Matemáticas, UNAM
Universidad Nacional Autónoma de México
Ciudad Universitaria
04510, México, D.F., MÉXICO
Abstract
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]}.
Keywords: circulant tournament, vertex colouring, heterochromatic number, heterochromatic triangle.
2000 Mathematic Subject Classification: 05C20, 05C15.
References
[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. |
Received 29 June 2001
Revised 13 May 2003