Choice-perfect graphs
Źsolt Tuza · Discussiones Mathematicae Graph Theory · 2012
Given a graph G = (V, E) and a set L v of admissible colors for each vertex v ∈ V (termed the list at v), a list coloring of G is a (proper) vertex coloring ϕ : V → v∈V L v such that ϕ(v) ∈ L v for all v ∈ V and ϕ(u) = ϕ(v) for all uv ∈ E. If such a ϕ exists, G is said to be list colorable.The choice number of G is the smallest natural number k for which G is list colorable whenever each list contains at least k colors.In this note we initiate the study of graphs in which the choice number equals the clique number or the chromatic number in every induced subgraph.We call them choice-ω-perfect and choice-χ-perfect graphs, respectively.The main result of the paper states that the square of every cycle is choice-χ-perfect.