@misc{SchiermeyerTuzaVoigt, author = {Schiermeyer, Ingo and Tuza, Zsolt and Voigt, Margit}, title = {On-line rankings of graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3011}, number = {SC-97-32}, abstract = {A (vertex) \$k\$-ranking of a graph \$G=(V,E)\$ is a mapping \$ p:V\to \{1,\dots,k\}\$ such that each path with endvertices of the same color \$i\$ contains an internal vertex of color \$\ge i+1\$. In the on-line coloring algorithms, the vertices \$v_1,\dots,v_n\$ arrive one by one in an unrestricted order, and only the edges inside the set \$\{v_1,\dots,v_i\}\$ are known when the color of \$v_i\$ has to be chosen. We characterize those graphs for which a 3-ranking can be found on-line. We also prove that the greedy (First-Fit) on-line algorithm, assigning the smallest feasible color to the next vertex at each step, generates a \$(3\log_2 n)\$-ranking for the path with \$n \geq 2\$ vertices, independently of the order in which the vertices are received.}, language = {en} } @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} } @misc{KratochvilTuza, author = {Kratochvil, Jan and Tuza, Zsolt}, title = {Rankings of Directed graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3030}, number = {SC-97-34}, abstract = {A ranking of a graph is a coloring of the vertex set with positive integers such that on every path connecting two vertices of the same color, there is a vertex of larger color. We consider the directed variant of this problem, where the above condition is imposed only on those paths in which all edges are oriented in the same direction. We show that the ranking number of a directed tree is bounded by that of its longest directed path plus one, and that it can be computed in polynomial time. Unlike the undirected case, however, deciding if the ranking number of a directed (and even of an acyclic directed) graph is bounded by a constant is NP-complete. In fact, the 3-ranking of planar bipartite acyclic digraphs is already hard.}, language = {en} } @misc{TuzaWagler, author = {Tuza, Zsolt and Wagler, Annegret}, title = {Minimally non-preperfect graphs of small maximum degree}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2971}, number = {SC-97-28}, abstract = {A graph \$G\$ is called preperfect if each induced subgraph \$G' \subseteq G\$ of order at least 2 has two vertices \$x,y\$ such that either all maximum cliques of \$G'\$ containing \$x\$ contain \$y\$, or all maximum indepentent sets of \$G'\$ containing \$y\$ contain \$x\$, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199-208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: \begin{itemize} \item[(i)] A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. \item[(ii)] If a graph \$G\$ is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if \$G\$ is bipartite, 3-edge-connected, regular of degree \$d\$ for some \$d \ge 3\$, and contains no 3-edge-connected \$d'\$-regular subgraph for any \$3 \le d' \le d\$. \end{itemize}}, language = {en} } @misc{Tuza, author = {Tuza, Zsolt}, title = {Graph coloring with local constraints - A survey}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3003}, number = {SC-97-31}, abstract = {We survey the literature on those variants of the {\em chromatic number\/} problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the {\em list colorings\/} and the {\em precoloring extensions\/} are considered. \par In one of the most general formulations, a graph \$G=(V,E)\$, sets \$L(v)\$ of admissible colors, and natural numbers \$c_v\$ for the vertices \$v\in V\$ are given, and the question is whether there can be chosen a subset \$C(v)\subseteq L(v)\$ of cardinality \$c_v\$ for each vertex in such a way that the sets \$C(v),C(v')\$ are disjoint for each pair \$v,v'\$ of adjacent vertices. The particular case of constant \$|L(v)|\$ with \$c_v=1\$ for all \$v\in V\$ leads to the concept of {\em choice number}, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. \par To illustrate typical techniques, some of the proofs are sketched.}, language = {en} }