✦ LIBER ✦

Graphs whose choice number is equal to their chromatic number

✍ Scribed by Gravier, Sylvain; Maffray, Fr�d�ric

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 219 KB
Volume: 27
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199802)27:2<87::aid-jgt4>3.0.co;2-b

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is k-choosable if it admits a vertex-coloring whenever the colors allowed at each vertex are restricted to a list of length k. If χ denotes the usual chromatic number of G, we are interested in which kind of G is χ-choosable. This question contains a famous conjecture, which states that every line-graph is χ-choosable. We present some other classes of graphs that are χ-choosable; all these classes are related to claw-free graphs.

📜 SIMILAR VOLUMES

On graphs whose domination numbers equal

On graphs whose domination numbers equal their independent domination numbers

✍ Belmannu Devadas Acharya; Purnima Gupta 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 185 KB

The total chromatic number of regular gr

The total chromatic number of regular graphs whose complement is bipartite

✍ J.K. Dugdale; A.J.W. Hilton 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 705 KB

We show that a regular graph G of order at least 6 whose complement c is bipartite has total chromatic number d(G) + 1 if and only if (i) G is not a complete graph, and (ii) G#K when n is even. As an aid in"';he proof of this, we also show that , for n>4, if the edges of a Hamiltonian path of Kzn a