On the upper chromatic number of (v3,b2)-configurations
A mixed hypergraph is a pair , where V is the vertex set and ( ) the edge (the co-edge) set of . A legal colouring of gives the same (different) colour(s) to at least two vertices of any co-edge (of any edge). The upper chromatic number of is the maximum number of colours that can be used in a legal colouring. After giving a general upper bound to , we here consider the co-hypergraph , where is a (v3,b2)-configuration over X. We prove that computing is NP-hard, but there exists a polynomial-time algorithm returning a colouring with colours. We also provide an example showing that this approximation factor is tight.
upper chromatic number hypergraphs computational complexity approximation algorithms