A mixed hypergraph is a pair H=(V; E U A), where V is the vertex set and E(A) the edge (the co-edge) set of H. A legal colouring of H gives the same (di0erent) colour(s) to at least two vertices of any co-edge (of any edge). The upper chromatic number of H is the maximum number x(H) of colours that can be used in a legal colouring. After giving a general upper bound to x(H), we here consider the co-hypergraph S=(X; 0 U T), where T is a (v3; b2)- configuration T over X . We prove that computing x(S) is NP-hard, but there exists a polynomial-time algorithm returning a colouring with 5/6 x(S) colours. We also provide an example showing that this approximation factor is tight.
On the upper chromatic number of (v3,b2)-configurations
FLAMMINI, MICHELE
2002-01-01
Abstract
A mixed hypergraph is a pair H=(V; E U A), where V is the vertex set and E(A) the edge (the co-edge) set of H. A legal colouring of H gives the same (di0erent) colour(s) to at least two vertices of any co-edge (of any edge). The upper chromatic number of H is the maximum number x(H) of colours that can be used in a legal colouring. After giving a general upper bound to x(H), we here consider the co-hypergraph S=(X; 0 U T), where T is a (v3; b2)- configuration T over X . We prove that computing x(S) is NP-hard, but there exists a polynomial-time algorithm returning a colouring with 5/6 x(S) colours. We also provide an example showing that this approximation factor is tight.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
