Brooks-type theorems for choosability with separation Export

@article{citeulike:788381, abstract = {We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ? V such that |L(v)| = p for all v ? V and |L(u) ? L(v)| ? c for all uv ? E, is it possible to find a ?list coloring,? i.e., a color f(v) ? L(v) for each v ? V, so that f(u) ? f(v) for all uv ? E? We prove that every of maximum degree \&Dgr; admits a list coloring for every such list assignment, provided p ? . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = Kn (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)). For planar graphs and c = 1, lists of length 4 suffice.}, address = {Department of Applied Mathematics, Charles University, Prague, Czech Republic; Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, Kende U.13 17, Hungary; Institut f\"{u}ur Mathematik, Technische Universit\"{a}t Ilmenau, Ilmenau, Germany}, author = {Kratochv\'{\i}l, J. and Tuza, Zs and Voigt, M.}, citeulike-article-id = {788381}, citeulike-linkout-0 = {http://dx.doi.org/10.1002/(SICI)1097-0118(199801)27:1%3C43::AID-JGT7%3E3.0.CO;2-G}, citeulike-linkout-1 = {http://www3.interscience.wiley.com/cgi-bin/abstract/35342/ABSTRACT}, doi = {10.1002/(SICI)1097-0118(199801)27:1%3C43::AID-JGT7%3E3.0.CO;2-G}, journal = {Journal of Graph Theory}, keywords = {graph\_theory, open\_problems}, number = {1}, pages = {43--49}, posted-at = {2006-08-07 04:39:19}, priority = {2}, title = {Brooks-type theorems for choosability with separation}, url = {http://dx.doi.org/10.1002/(SICI)1097-0118(199801)27:1%3C43::AID-JGT7%3E3.0.CO;2-G}, volume = {27}, year = {1998} }

TY - JOUR ID - citeulike:788381 L3 - citeulike-article-id:788381 N2 - We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ? V such that |L(v)| = p for all v ? V and |L(u) ? L(v)| ? c for all uv ? E, is it possible to find a ?list coloring,? i.e., a color f(v) ? L(v) for each v ? V, so that f(u) ? f(v) for all uv ? E? We prove that every of maximum degree &Dgr; admits a list coloring for every such list assignment, provided p ? . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = Kn (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)). For planar graphs and c = 1, lists of length 4 suffice. IS - 1 JF - Journal of Graph Theory AD - Department of Applied Mathematics, Charles University, Prague, Czech Republic; Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, Kende U.13 17, Hungary; Institut füur Mathematik, Technische Universität Ilmenau, Ilmenau, Germany EP - 49 TI - Brooks-type theorems for choosability with separation VL - 27 SP - 43 KW - graph_theory KW - open_problems AU - Kratochvíl, J AU - Tuza, Zs AU - Voigt, M PY - 1998/// UR - http://dx.doi.org/10.1002/(SICI)1097-0118(199801)27:1%3C43::AID-JGT7%3E3.0.CO;2-G ER -