Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: choice-perfect graph

Sortuj według:

Ogranicz wyniki do:

Choice-Perfect Graphs

100%

Tuza Z.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 1

231-242

Given a graph G = (V,E) and a set Lv of admissible colors for each vertex v ∈ V (termed the list at v), a list coloring of G is a (proper) vertex coloring ϕ : V → S v2V Lv such that ϕ(v) ∈ Lv for all v ∈ V and ϕ(u) 6= ϕ(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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Tuza Z.

1 2013

Wyniki wyszukiwania

Choice-Perfect Graphs