Originators: Radoslav Kirov and Ramin Naimi (presented by Wipawee Tangjai - REGS 2010)
Definitions: An k-uniform list assignment is an assignment of k available colors to each vertex of a graph G. When L is a k-uniform list assignment on G, let col(G,L) be the number of proper colorings of G such that the color on each vertex v is chosen from its list L(v). Let col(G,k) be the number of proper colorings of G when L={1,...,k}. A graph G is k-monophilic if col(G,k) ≤ col(G,L) for every k-uniform list assignment L. The core of a graph is obtained by iterating deleting leaves.
Background: To maximize the probability of getting a non-proper coloring of a graph from a k-uniform list assigment, intuitively it seems like we should give every vertices the same list. This is the property captured by being k-monophilic. However, there are graphs for which the probability of non-proper colorings when giving identical lists is less than for some lists that are not identical. If k<χ(G), then G is k-monophilic. If χ(G)≤k<χl(G), where χl(G) is the list chromatic number of G, then G is not k-monophilic.
In 1990, Kostochka and Sidorenko (unpublished) proved that chordal graphs are k-monophilic for all k. Kirov and Naimi [KN] proved that cycles are k-monophilic for k≥2. They also proved that a connected graph is 2-monophilic if and only if its core is a single vertex, is a cycle, is K2,3, or contains an odd cycle. This result uses Rubin's Block Theorem, which characterizes the connected 2-choosable graphs as those whose core is a single vertex, an even cycle, or the union of paths of length 2, 2, and 2k having common endpoints.
Question 1: When k>2, is the cartesian product of two k-monophilic graphs always k-monophilic?
Comments: The implication does not hold when k=2, since the cartesian product of P3 and K2 is well known to be 2-colorable but not 2-choosable.
Question 2: Does there exist k such that k is the smallest, for which G is k-colorable and k-monophilic an, and k is the smallest such that G is k'-monophilic for all k'≤k.
Question 3: If a graph is k-colorable and k-monophilic, is it necessarily (k+1)-monophilic?
Comments: The results of [D] suggest two reasonable ways to define the monophilic number of a graph G. First is the smallest k such that G is k-colorable and k-monophilic. Alternatively, it could be the smallest k such that G is k'-monophilic for all k'≤k. If the answer to Question 3 is yes, then the two definitions are equivlent.
References:
[KN] Kirov, Radoslav; Naimi, Ramin. List Coloring and n-Monophilic Graphs.
7 July 2010.
on the Arxiv at http://arxiv.org/PS_cache/arxiv/pdf/1004/1004.5183v1.pdf.
[D] Q. Donner. On the number of list-colorings. Journal of Graph Theory
16 (1992), 239-245.