Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 5 of 5
Back to Result List

Graph coloring with local constraints - A survey

Please always quote using this URN: urn:nbn:de:0297-zib-3003
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Zsolt Tuza
Document Type:ZIB-Report
Date of first Publication:1997/07/10
Series (Serial Number):ZIB-Report (SC-97-31)
ZIB-Reportnumber:SC-97-31
Published in:Appeared in: Discussiones Mathematicae - Graph Theory 17, No. 2 (1997) pp. 161-228
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.