List-Coloring and Chromatic-Choosability -- A Dynamic Survey
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
Abstract
List-coloring, introduced independently by Vizing and by Erdős, Rubin, and Taylor in the 1970s, generalizes ordinary vertex coloring by assigning to each vertex its own set of admissible colors.
A graph is chromatic-choosable if its list chromatic number equals its chromatic number.
The previous survey on list-coloring by D R Woodall (2001), emphasized defective choosability, the list-coloring conjectures, and different methods used for list-coloring.
This survey reviews major developments on list-coloring and chromatic-choosability, with emphasis on graph classes for which equality is known, graph classes exhibiting a nontrivial gap, and the principal methods used to prove such results.
The survey covers embedded graphs, perfect graphs, complete bipartite and multipartite graphs, claw-free graphs, line graphs, powers of graphs, graph products, and selected variants of list-coloring.