The Dichromatic Number of Infinite Families of Circulant Tournaments

Nahid Javier, and Bernardo Llano. "The Dichromatic Number of Infinite Families of Circulant Tournaments." Discussiones Mathematicae Graph Theory 37.1 (2017): 221-238. <http://eudml.org/doc/287990>.

@article{NahidJavier2017,
abstract = {The dichromatic number dc(D) of a digraph D is defined to be the minimum number of colors such that the vertices of D can be colored in such a way that every chromatic class induces an acyclic subdigraph in D. The cyclic circulant tournament is denoted by [...] T=C→2n+1(1,2,…,n) $T = \overrightarrow\{C\} _\{2n + 1\} (1,2, \ldots ,n)$ , where V (T) = ℤ2n+1 and for every jump j ∈ 1, 2, . . . , n there exist the arcs (a, a + j) for every a ∈ ℤ2n+1. Consider the circulant tournament [...] C→2n+1〈k〉 $\overrightarrow\{C\} _\{2n + 1\} \left\langle k \right\rangle $ obtained from the cyclic tournament by reversing one of its jumps, that is, [...] C→2n+1 〈k〉 $\overrightarrow\{C\} _\{2n + 1\} \left\langle k \right\rangle $ has the same arc set as [...] C→2n+1(1,2,…,n) $\overrightarrow\{C\} _\{2n + 1\} (1,2, \ldots ,n)$ except for j = k in which case, the arcs are (a, a − k) for every a ∈ ℤ2n+1. In this paper, we prove that [...] dc(C→2n+1 〈k〉)∈2,3,4 $dc ( \{\overrightarrow\{C\} _\{2n + 1\} \left\langle k \right\rangle \} ) \in \lbrace 2,3,4\rbrace $ for every k ∈ 1, 2, . . . , n. Moreover, we classify which circulant tournaments [...] C→2n+1 〈k〉 $\overrightarrow\{C\} _\{2n + 1\} \left\langle k \right\rangle $ are vertex-critical r-dichromatic for every k ∈ 1, 2, . . . , n and r ∈ 2, 3, 4. Some previous results by Neumann-Lara are generalized.},
author = {Nahid Javier, Bernardo Llano},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {tournament; dichromatic number; vertex-critical r-dichromatic tournament; vertex-critical -dichromatic tournament},
language = {eng},
number = {1},
pages = {221-238},
title = {The Dichromatic Number of Infinite Families of Circulant Tournaments},
url = {http://eudml.org/doc/287990},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Nahid Javier
AU - Bernardo Llano
TI - The Dichromatic Number of Infinite Families of Circulant Tournaments
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 1
SP - 221
EP - 238
AB - The dichromatic number dc(D) of a digraph D is defined to be the minimum number of colors such that the vertices of D can be colored in such a way that every chromatic class induces an acyclic subdigraph in D. The cyclic circulant tournament is denoted by [...] T=C→2n+1(1,2,…,n) $T = \overrightarrow{C} _{2n + 1} (1,2, \ldots ,n)$ , where V (T) = ℤ2n+1 and for every jump j ∈ 1, 2, . . . , n there exist the arcs (a, a + j) for every a ∈ ℤ2n+1. Consider the circulant tournament [...] C→2n+1〈k〉 $\overrightarrow{C} _{2n + 1} \left\langle k \right\rangle $ obtained from the cyclic tournament by reversing one of its jumps, that is, [...] C→2n+1 〈k〉 $\overrightarrow{C} _{2n + 1} \left\langle k \right\rangle $ has the same arc set as [...] C→2n+1(1,2,…,n) $\overrightarrow{C} _{2n + 1} (1,2, \ldots ,n)$ except for j = k in which case, the arcs are (a, a − k) for every a ∈ ℤ2n+1. In this paper, we prove that [...] dc(C→2n+1 〈k〉)∈2,3,4 $dc ( {\overrightarrow{C} _{2n + 1} \left\langle k \right\rangle } ) \in \lbrace 2,3,4\rbrace $ for every k ∈ 1, 2, . . . , n. Moreover, we classify which circulant tournaments [...] C→2n+1 〈k〉 $\overrightarrow{C} _{2n + 1} \left\langle k \right\rangle $ are vertex-critical r-dichromatic for every k ∈ 1, 2, . . . , n and r ∈ 2, 3, 4. Some previous results by Neumann-Lara are generalized.
LA - eng
KW - tournament; dichromatic number; vertex-critical r-dichromatic tournament; vertex-critical -dichromatic tournament
UR - http://eudml.org/doc/287990
ER -