Claw-free circular-perfect graphs
PÊCHER, Arnaud
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmes Parallèles et Optimisation [IRIT-APO]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmes Parallèles et Optimisation [IRIT-APO]
PÊCHER, Arnaud
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmes Parallèles et Optimisation [IRIT-APO]
< Reduce
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Algorithmes Parallèles et Optimisation [IRIT-APO]
Language
en
Article de revue
This item was published in
Journal of Graph Theory. 2010, vol. 65, n° 2, p. 163-172
Wiley
English Abstract
The circular chromatic number of a graph is a well-studied refinement of the chromatic number. Circular-perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This paper ...Read more >
The circular chromatic number of a graph is a well-studied refinement of the chromatic number. Circular-perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This paper studies claw-free circular-perfect graphs. First we prove that if $G$ is a connected claw-free circular-perfect graph with $\chi(G) > \omega(G)$, then $\min\{\alpha(G), \omega(G)\} =2$. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw-free circular-perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs $G$ have $\min \{\alpha(G), \omega(G)\} = 2$. In contrast to this result, it is shown in \cite{PanZhu2006} that minimal circular-imperfect graphs $G$ can have arbitrarily large independence number and arbitrarily large clique number. In this paper, we prove that claw-free minimal circular-imperfect graphs $G$ have $\min \{\alpha(G), \omega(G)\} \leq 3$.Read less <
ANR Project
/ - ANR-09-BLAN-0373
Origin
Hal imported