Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

Dichromatic number, circulant tournaments and Zykov sums of digraphs

Víctor Neumann-Lara — 2000

Discussiones Mathematicae Graph Theory

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

On the heterochromatic number of circulant digraphs

Hortensia Galeana-SánchezVíctor Neumann-Lara — 2004

Discussiones Mathematicae Graph Theory

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 h c ( D n , s ) 5 for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].

Page 1

Download Results (CSV)