- Tytuł:
- The Dichromatic Number of Infinite Families of Circulant Tournaments
- Autorzy:
-
Javier, Nahid
Llano, Bernardo - Powiązania:
- https://bibliotekanauki.pl/articles/31342132.pdf
- Data publikacji:
- 2017-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
tournament
dichromatic number
vertex-critical r -dichromatic tournament - Opis:
- 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= \vec{C}_{2n+1}(1,2,…,n) $, where $ V (T) = \mathbb{ℤ}_{2n+1}$ and for every jump $ j \in {1, 2, . . ., n} $ there exist the arcs $ (a, a + j)$ for every $ a \in \mathbb{Z}_{2n+1} $. Consider the circulant tournament $ \vec{C}_{2n+1} 〈k〉 $ obtained from the cyclic tournament by reversing one of its jumps, that is, $ \vec{C}_{2n+1} 〈k〉 $ has the same arc set as $ \vec{C}_{2n+1} (1,2,…,n) $ except for $j = k$ in which case, the arcs are $(a, a − k)$ for every $ a \in \mathbb{Z}_{2n+1} $. In this paper, we prove that $ dc (\vec{C}_{2n+1} 〈k〉 ) \in {2,3,4} $ for every $ k \in {1, 2, . . ., n} $. Moreover, we classify which circulant tournaments $ \vec{C}_{2n+1} 〈k〉 $ are vertex-critical $r$-dichromatic for every $ k \in {1, 2, . . ., n} $ and $ r \in {2, 3, 4} $. Some previous results by Neumann-Lara are generalized.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 221-238
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł