Amenable colorings

✍ Scribed by N.V.R. Mahadev; Fred S. Roberts

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 958 KB
• Volume: 76
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00127-8

✦ Synopsis

We investigate graph colorings that satisfy the restraint that the color assigned to a given vertex must belong to a set of allowable colors or the restraint that it must not belong to a set of disallowed colors. Following ErdGs et al.

[lo], we say that the graph G is k-choosable if whenever sets S(n) of size k are assigned to vertices x of G, there is an ordinary graph coloring of G so that the color assigned to x belongs to S(x). Following Brown et al. , we say that G is (j, m)-amenable if whenever subsets R(x) of { 1,2,. , m} of size j are assigned to vertices x of G, there is an ordinary graph coloring using colors in { 1,2,. , m} so that the color assigned to x does not belong to the set R(n). We shall observe that for any graph G and positive integer k, there is a number J,(G) which is either a nonnegative integer or 00, so that for any positive integer j, G is (j,j+k)-amenable if and only if j < Jk(G). It is straightforward that G is k-choosable if and only if it is k-colorable and Jk(G) = co. We study the problem of identifying graphs with Jk(G) =J.