The Dichromatic Number of Infinite Families of Circulant Tournaments
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2017-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1930 |
| _version_ | 1797757781286060032 |
|---|---|
| author | Javier Nahid Llano Bernardo |
| author_facet | Javier Nahid Llano Bernardo |
| author_sort | Javier Nahid |
| collection | DOAJ |
| description | 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 \{ 2,3,4\}$ 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. |
| first_indexed | 2024-03-12T18:19:31Z |
| format | Article |
| id | doaj.art-b53cae667d77473e900fa6e83603a33a |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:31Z |
| publishDate | 2017-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-b53cae667d77473e900fa6e83603a33a2023-08-02T08:59:10ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922017-02-0137122123810.7151/dmgt.1930dmgt.1930The Dichromatic Number of Infinite Families of Circulant TournamentsJavier Nahid0Llano Bernardo1Departamento de Matemáticas, Universidad Autónoma Metropolitana Iztapalapa, San Rafael Atlixco 186, Colonia Vicentina, 09340, México, D.F., MexicoDepartamento de Matemáticas, Universidad Autónoma Metropolitana Iztapalapa, San Rafael Atlixco 186, Colonia Vicentina, 09340, México, D.F., MexicoThe 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 \{ 2,3,4\}$ 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.https://doi.org/10.7151/dmgt.1930tournamentdichromatic numbervertex-critical r-dichromatic tournament05c2005c38 |
| spellingShingle | Javier Nahid Llano Bernardo The Dichromatic Number of Infinite Families of Circulant Tournaments Discussiones Mathematicae Graph Theory tournament dichromatic number vertex-critical r-dichromatic tournament 05c20 05c38 |
| title | The Dichromatic Number of Infinite Families of Circulant Tournaments |
| title_full | The Dichromatic Number of Infinite Families of Circulant Tournaments |
| title_fullStr | The Dichromatic Number of Infinite Families of Circulant Tournaments |
| title_full_unstemmed | The Dichromatic Number of Infinite Families of Circulant Tournaments |
| title_short | The Dichromatic Number of Infinite Families of Circulant Tournaments |
| title_sort | dichromatic number of infinite families of circulant tournaments |
| topic | tournament dichromatic number vertex-critical r-dichromatic tournament 05c20 05c38 |
| url | https://doi.org/10.7151/dmgt.1930 |
| work_keys_str_mv | AT javiernahid thedichromaticnumberofinfinitefamiliesofcirculanttournaments AT llanobernardo thedichromaticnumberofinfinitefamiliesofcirculanttournaments AT javiernahid dichromaticnumberofinfinitefamiliesofcirculanttournaments AT llanobernardo dichromaticnumberofinfinitefamiliesofcirculanttournaments |