On the heterochromatic number of circulant digraphs

Hortensia 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 -