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.
2002
Upper chromatic number; Hypergraphs; Computational complexity; Approximation algorithms
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/2153
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact