# On the heterochromatic number of circulant digraphs

Hortensia Galeana-Sánchez; Víctor Neumann-Lara

Discussiones Mathematicae Graph Theory (2004)

- Volume: 24, Issue: 1, page 73-79
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHortensia Galeana-Sánchez, and Víctor Neumann-Lara. "On the heterochromatic number of circulant digraphs." Discussiones Mathematicae Graph Theory 24.1 (2004): 73-79. <http://eudml.org/doc/270660>.

@article{HortensiaGaleana2004,

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 $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].},

author = {Hortensia Galeana-Sánchez, Víctor Neumann-Lara},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {circulant tournament; vertex colouring; heterochromatic number; heterochromatic triangle},

language = {eng},

number = {1},

pages = {73-79},

title = {On the heterochromatic number of circulant digraphs},

url = {http://eudml.org/doc/270660},

volume = {24},

year = {2004},

}

TY - JOUR

AU - Hortensia Galeana-Sánchez

AU - Víctor Neumann-Lara

TI - On the heterochromatic number of circulant digraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2004

VL - 24

IS - 1

SP - 73

EP - 79

AB - 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].

LA - eng

KW - circulant tournament; vertex colouring; heterochromatic number; heterochromatic triangle

UR - http://eudml.org/doc/270660

ER -

## References

top- [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. Zbl0931.05030
- [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. Zbl0776.05079
- [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. Zbl0969.05031
- [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. Zbl0864.05035
- [7] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197-198 (1999) 617-632. Zbl0928.05033