×

Colorability of mixed hypergraphs and their chromatic inversions. (English) Zbl 1271.05070

Summary: 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 \(\underline{\mathbf c}\)ommon color and every D-edge has two vertices with \(\underline{\mathbf d}\)ifferent 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 whether 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\neq 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.

MSC:

05C65 Hypergraphs
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bacsó G, Bujtás Cs, Tuza Zs, Voloshin VI (2008) New challenges in the theory of hypergraph coloring. In: Acharya BD et al (eds) Advances in discrete mathematics and applications. Ramanujan Mathematical Society Lecture Notes Series, vol 13, Mysore, pp 45-57 (2010) · Zbl 1231.05187
[2] Bujtás Cs (2008) Algorithms and structure: set partitions under local constraints. PhD Thesis, Information Science& Technology PhD School, University of Pannonia, Hungary · Zbl 0943.05035
[3] Bujtás Cs, Tuza Zs (2007) Color-bounded hypergraphs, III: model comparison. Appl Anal Discr Math 1:36-55 · Zbl 1246.05053 · doi:10.2298/AADM0701036B
[4] Jiang T, Mubayi D, Voloshin V, West DB (2002) The chromatic spectrum of mixed hypergraphs. Graphs Combin 18:309-318 · Zbl 0994.05063 · doi:10.1007/s003730200023
[5] Lovász L (1973) Coverings and colorings of hypergraphs. Congr Numer 8:3-12 · Zbl 0322.05114
[6] Phelps KT, Rödl V (1984) On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems. Combinatorica 4:79-88 · Zbl 0535.68030 · doi:10.1007/BF02579160
[7] Tuza Zs, Voloshin VI (2000) Uncolorable mixed hypergraphs. Discr Appl Math 99:209-227 · Zbl 0943.05035 · doi:10.1016/S0166-218X(99)00134-1
[8] Voloshin VI (1993) The mixed hypergraphs. Comput Sci J Moldova 1:45-52
[9] Voloshin VI (1995) On the upper chromatic number of a hypergraph. Australas J Combin 11:25-45 · Zbl 0827.05027
[10] Voloshin VI (2006) Mixed hypergraph coloring web site http://spectrum.troy.edu/ voloshin/mh.html · Zbl 0827.05027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.