Choice number of 3-colorable elementary graphs

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

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 394 KB
• Volume: 165-166
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00182-3

✦ Synopsis

We show that the choice number of a graph G is equal to its chromatic number when G belongs to a restricted class of claw-free graphs, in view of the conjecture that this is true for every claw-free graph.

We consider only finite, undirected graphs, without loops. Given a graph G = ( V, E), a k-coloring of the vertices of G is a mapping c : V + { 1,2,. . , k} such that for every edge my of G we have c(x) # c(y). The graph G is called k-colorable if it admits a k-coloring, and x(G) denotes the smallest of all integers k such that G is k-colorable. ErdGs et al.

[2] introduced a variant of the coloring problem as follows. Suppose that each vertex u is assigned a list L(V) of possible colors; we then want to find a vertex-coloring c such that c(v) t L(u) for all 2: E V. When such a c exists we will say that the graph G is L-colorable; we may also say that c is an L-coloring of G.

Given an integer k, the graph G is called k-choosahle if it is L-colorable for every