کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656721 | 1632974 | 2016 | 24 صفحه PDF | دانلود رایگان |
Let G be a plane graph with outer cycle C and let (L(v):v∈V(G))(L(v):v∈V(G)) be a family of sets such that |L(v)|≥5|L(v)|≥5 for every v∈V(G)v∈V(G). By an L-coloring of a subgraph J of G we mean a (proper) coloring ϕ of J such that ϕ(v)∈L(v)ϕ(v)∈L(v) for every vertex v of J. We prove a conjecture of Dvořák et al. that if H is a minimal subgraph of G such that C is a subgraph of H and every L-coloring of C that extends to an L-coloring of H also extends to an L-coloring of G , then |V(H)|≤19|V(C)||V(H)|≤19|V(C)|.This is a lemma that plays an important role in subsequent papers, because it motivates the study of graphs embedded in surfaces that satisfy an isoperimetric inequality suggested by this result. Such study turns out to be quite profitable for the subject of list coloring graphs on surfaces.
Journal: Journal of Combinatorial Theory, Series B - Volume 119, July 2016, Pages 42–65