Uniquely colorable mixed hypergraphs
type: Item
instance of: scholarly article
title: Uniquely colorable mixed hypergraphs
zbMATH Open document ID: 0990.05044
DOI: 10.1016/S0012-365X(01)00176-5
author: Zsolt Tuza
author: Huishan Zhou
author: V. I. Voloshin
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: A mixed hypergraph consists of two families of edges: the \({\mathcal C}\)-edges and \({\mathcal D}\)-edges. In a coloring, every \({\mathcal C}\)-edge has at least two vertices of the same color, while every \({\mathcal D}\)-edge has at least two vertices colored differently. The largest and smallest possible numbers of colors in a coloring are termed the upper and lower chromatic number, \(\overline{\chi}\) and \(\chi \), respectively. A mixed hypergraph is called uniquely colorable if it has precisely one coloring apart from the permutation of colors. In this paper it is shown that every colorable mixed hypergraph can be embedded into some uniquely colorable mixed hypergraph; the role of uniquely colorable subhypergraphs being separators is investigated, recursive operations (orderings and subset contractions) and unique colorings are studied, and it is proved that it is NP-hard to decide whether a mixed hypergraph is uniquely colorable. Also the weaker property where the mixed hypergraph has a unique coloring with \(\overline {\chi}\) colors and a unique coloring with \(\chi \) colors, where \(\overline {\chi}>\chi \) is discussed. Note that the class of these ``weakly uniquely colorable'' mixed hypergraphs contains all uniquely colorable graphs in the usual sense.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1746261
zbMATH Keywords: coloring
zbMATH Keywords: mixed hypergraph
zbMATH Keywords: lower (upper) chromatic number
zbMATH Keywords: unique colorability
zbMATH Keywords: algorithmic complexity
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1746261