𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the choice number of claw-free perfect graphs

✍ Scribed by Sylvain Gravier; Frédéric Maffray

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
273 KB
Volume
276
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that every 3-chromatic claw-free perfect graph is 3-choosable.

📜 SIMILAR VOLUMES

A Description of Claw-Free Perfect Graph
A Description of Claw-Free Perfect Graphs
✍ Frédéric Maffray; Bruce A. Reed 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 249 KB

It is known that all claw-free perfect graphs can be decomposed via clique-cutsets into two types of indecomposable graphs respectively called elementary and peculiar (1988, V. Chva tal and N. Sbihi, J. Combin. Theory Ser. B 44, 154 176). We show here that every elementary graph is made up in a well

A polynomial algorithm for the minimum w
A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs
✍ Wen-Lian HSU; George L. Nemhauser 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 688 KB

Discrete Mathematics 3X ( 19X2) 6S-71 North-Holland Publishing Company 65 Let G = (V, E) be a graph with a positive number wt(v) assigned to each L' E V. A weighted clique saver of the vertices of G is a collection of cliques with a non-negative weight yC. assigned to each clique C in the collection

Cubicity of interval graphs and the claw
Cubicity of interval graphs and the claw number
✍ Abhijin Adiga; L. Sunil Chandran 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 1 views

Let G(V , E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b-dimensional cube is a Cartesian product I 1 ×I 2 ו • •×I b , where each I i is a closed interval of unit length on the real line. The cubicity of G, denoted by cub(G), is the minimum positive in

On factors of 4-connected claw-free grap
On factors of 4-connected claw-free graphs
✍ H. J. Broersma; M. Kriesell; Z. Ryjác̆ek 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian,

Claw-free cubic graphs with clique-trans
Claw-free cubic graphs with clique-transversal number half of their order
✍ Erfang Shan; Haichao Wang 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 362 KB

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by τ C (G), is the minimum cardinality of a cliquetransversal set in G. In 2008, we showed that the clique-transversal number of every clawfree cubic graph is

On linear and circular structure of (cla
On linear and circular structure of (claw, net)-free graphs
✍ Andreas Brandstädt; Feodor F. Dragan 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 289 KB

We prove that every (claw, net)-free graph contains an induced doubly dominating cycle or a dominating pair. Moreover, using LexBFS we present a linear time algorithm which, for a given (claw, net)-free graph, ÿnds either a dominating pair or an induced doubly dominating cycle. We show also how one