@misc{TuzaVoloshin, author = {Tuza, Zsolt and Voloshin, Vitaly I.}, title = {Uncolorable mixed hypergraphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3024}, number = {SC-97-33}, abstract = {A mixed hypergraph \${\cal H}=(X,{\cal A},{\cal E})\$ consists of the vertex set \$X\$ and two families of subsets: the family of edges \${\cal E}\$ and the family of co-edges \${\cal A}\$. In a coloring every edge \$E \in {\cal E}\$ has at least two vertices of different colors, while every co-edge \$A \in {\cal A}\$ has at least two vertices of the same color. The smallest (largest) number of colors for which there exists a coloring of a mixed hypergraph \$\cal H\$ using all the colors is called the lower (upper) chromatic number and is denoted \$\chi ({\cal H})\$ \$(\bar {\chi} ({\cal H}) )\$. A mixed hypergraph is called uncolorable if it admits no coloring. \par We show that there exist uncolorable mixed hypergraphs \${\cal H}=\$ \$(X, {\cal A}, {\cal E})\$ with arbitrary difference between the upper chromatic number \$\bar{\chi } ({\cal H}_{\cal A}) \$ of \${\cal H}_{\cal A}=(X,{\cal A})\$ and the lower chromatic number \${\chi }({\cal H}_{\cal E})\$ of \${\cal H}_{\cal E}=(X,{\cal E}).\$ Moreover, for any \$k=\bar \chi ({\cal H}_{\cal A})- \chi ({\cal H}_{\cal E})\$, the minimum number \$v(k)\$ of vertices of an inclusionwise minimal uncolorable mixed hypergraph is exactly \$k+4.\$ \par We introduce the measure of uncolorability which is called the vertex uncolorability number and propose a greedy algorithm that finds an estimate on it, and is a mixed hypergraph coloring heuristic at the same time. \par We show that the colorability problem can be expressed as an integer linear programming problem. \par Concerning particular cases, we describe those complete \$(l,m)\$-uniform mixed hypergraphs which are uncolorable, and observe that for given \$(l,m)\$ almost all complete \$(l,m)\$-uniform mixed hypergraphs are uncolorable, whereas generally almost all complete mixed hypergraphs are colorable.}, language = {en} }