Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: dichromatic number

Sortuj według:

Ogranicz wyniki do:

The Dichromatic Number of Infinite Families of Circulant Tournaments

100%

Javier N., Llano B.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 1

221-238

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.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Dichromatic number, circulant tournaments and Zykov sums of digraphs

75%

Neumann-Lara V.

Discussiones Mathematicae Graph Theory

2000

tom 20

nr 2

197-207

The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic circulant tournaments for every k ≥ 3, k ≠ 7.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Javier N.

1 Llano B.

1 Neumann-Lara V.

1 2017

1 2000

Wyniki wyszukiwania

The Dichromatic Number of Infinite Families of Circulant Tournaments

Dichromatic number, circulant tournaments and Zykov sums of digraphs