Colorability of mixed hypergraphs and their chromatic inversions

Máté Hegyháti and Zsolt Tuza ()
Additional contact information
Máté Hegyháti: University of Pannonia
Zsolt Tuza: University of Pannonia

Journal of Combinatorial Optimization, 2013, vol. 25, issue 4, No 19, 737-751

Abstract: Abstract We solve a long-standing open problem concerning a discrete mathematical model, which has various applications in computer science and several other fields, including frequency assignment and many other problems on resource allocation. A mixed hypergraph $$\mathcal H $$ is a triple $$(X,\mathcal C ,\mathcal D )$$ , where $$X$$ is the set of vertices, and $$\mathcal C $$ and $$\mathcal D $$ are two set systems over $$X$$ , the families of so-called C-edges and D-edges, respectively. A vertex coloring of a mixed hypergraph $$\mathcal H $$ is proper if every C-edge has two vertices with a common color and every D-edge has two vertices with different colors. A mixed hypergraph is colorable if it has at least one proper coloring; otherwise it is uncolorable. The chromatic inversion of a mixed hypergraph $$\mathcal H =(X,\mathcal C ,\mathcal D )$$ is defined as $$\mathcal H ^c=(X,\mathcal D ,\mathcal C )$$ . Since 1995, it was an open problem wether there is a correlation between the colorability properties of a hypergraph and its chromatic inversion. In this paper we answer this question in the negative, proving that there exists no polynomial-time algorithm (provided that $$P \ne NP$$ ) to decide whether both $$\mathcal H $$ and $$\mathcal H ^c$$ are colorable, or both are uncolorable. This theorem holds already for the restricted class of 3-uniform mixed hypergraphs (i.e., where every edge has exactly three vertices). The proof is based on a new polynomial-time algorithm for coloring a special subclass of 3-uniform mixed hypergraphs. Implementation in C++ programming language has been tested. Further related decision problems are investigated, too.

Keywords: Hypergraph coloring; Algorithmic complexity; Mixed hypergraph; Chromatic inversion (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9559-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:25:y:2013:i:4:d:10.1007_s10878-012-9559-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9559-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().