- Tytuł:
- Choice-Perfect Graphs
- Autorzy:
- Tuza, Zsolt
- Powiązania:
- https://bibliotekanauki.pl/articles/30146654.pdf
- Data publikacji:
- 2013-03-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph coloring
list coloring
choice-perfect graph - Opis:
- Given a graph $ G = (V,E) $ and a set $ L_v $ of admissible colors for each vertex $ v \in V $ (termed the list at $v$), a list coloring of $G$ is a (proper) vertex coloring $ \phi : V \rightarrow \bigcup \text{}_{v \in V} L_v $ such that $ \phi (v) \in L_v $ for all $ v \in V $ and $ \phi(u) \ne \phi(v) $ for all $ uv \in E $. If such a $ \phi $ 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 231-242
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki