The search session has expired. Please query the service again.
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...
Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs where the stable set polytope coincides with the fractional stable set polytope . For all imperfect graphs it holds that . It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss three...
Perfect graphs constitute a well-studied graph class with a rich
structure, reflected by many characterizations with respect to
different concepts.
Perfect graphs are, for instance, precisely those graphs G
where the stable set polytope STAB(G) coincides
with the fractional stable set polytope QSTAB(G).
For all imperfect graphs G it holds that STAB(G) ⊂ QSTAB(G).
It is, therefore, natural to use the difference between the two polytopes
in order to decide how far an imperfect graph is away...
A β-perfect graph is a simple graph G such that χ(G') = β(G') for every induced subgraph G' of G, where χ(G') is the chromatic number of G', and β(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., δ(H)+1). The vertices of a β-perfect graph G can be coloured with χ(G) colours in polynomial time (greedily).
The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden induced subgraphs,...
Currently displaying 1 –
4 of
4