Compact compatible topologies for graphs with small cycles.
Dichromatic number, circulant tournaments and Zykov sums of digraphs
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...
A class of tight circulant tournaments
A tournament is said to be tight whenever every 3-colouring of its vertices using the 3 colours, leaves at least one cyclic triangle all whose vertices have different colours. In this paper, we extend the class of known tight circulant tournaments.
On the heterochromatic number of circulant digraphs
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 be the oriented graph such that is the set of integers mod 2n+1 and In this paper we prove that for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].
A note on minimally 3-connected graphs
If G is a minimally 3-connected graph and C is a double cover of the set of edges of G by irreducible walks, then |E(G)| ≥ 2| C| - 2.
Page 1