Originators: Uwe Schauz, Xuding Zhu (presented by Thomas Mahoney - REGS 2011)
Definitions: Introduced by Schauz [S1], the Marker/Remover game (originally called "Mr. Paint and Mrs. Correct") is played on a graph G. For each v∈V(G), there are f(v) erasers available. On each round, first Marker marks a subset of the vertices, and then Remover selects an independent set from the marked vertices. This independent set is removed from the graph, and for each vertex that was marked but not removed, Remover must use one of its erasers to erase the mark. Marker wins if Remover cannot remove an independent set of marked vertices and erase the remaining marks. (For example, this will occur if Remover runs out of erasers at two adjacent vertices.) Remover wins if the entire graph has been removed, meaning that the removed sets form a proper coloring.
A graph G is k-paintable if Remover has a winning strategy whenever k-1 erasers are available at each vertex. The least such k is the paintability or paint number of G, written χp(G). More generally, G is f-paintable if Remover has a winning strategy when f(v)-1 erasers are available at v, for each vertex v. Similarly, G is k-edge-paintable if L(G) is k-paintable (matchings are removed from G), and the least such k is the edge-paintability or edge-paint number or paint index of G, written χ'p(G).
Background: Every k-paintable graph is k-choosable, where a graph is k-choosable if a proper coloring can be chosen from lists of colors assigned to the vertices whenever the assigned lists all have size at least k. Suppose that G is k-paintable. Given a k-uniform assignment of color lists to the vertices of G, Remover pretends that on round j Marker marks the set of vertices having color j in their lists. Remover follows a winning strategy against this strategy, selecting in round j the independent set of vertices to receive color j from their lists. Since G is k-paintable, Remover assigns each vertex a color by the time the k colors in its list are exhausted.
The terminology for choosability or choice number χl(G) (l for "list") is analogous to that for paintability. Just as some bounds on chromatic number have been proved to hold also for choice number, so Schauz proved that some bounds on choice number also hold for paint number. It is well-known that k-degenerate graphs are k+1-colorable and k+1-choosable; it is a pleasant exercise to show also that they are k+1-paintable. More significantly, the hypothesis that by the Alon-Tarsi Theorem implies f-choosability also suffices for f-paintability [S2]. Similarly, planar graphs are 5-paintable [S1], bipartite graphs are Δ(G)-edge-paintable [S1], and bipartite planar graphs are 3-paintable [S2].
As suggested by Zhu [Z], the Marker/Remover game can be view as "On-line list coloring"; Remover sees the lists one color at a time and must irrevocably decide then the independent set to choose that color, but the number of chances for each vertex is limited. Upper bounds by Zhu [Z] include χp(G ≤1+χ(G)ln n, also χp(G ≤3 when χl(G)≤2, and a characterization of graphs G such that χp(G ≤2. In particular, a connected graph is 2-paintable if and only if its core is K1, C2n, or K2,3, where the core of a connected graph is the graph obtained by iteratively deleting vertices of degree 1. (The characterization of 2-choosable graphs in [ERT] allows a bit more flexibility; instead of K2,3, any graph obtained by expanding one of the vertices of degree 2 into a path of even length is allowed.)
A graph G is chromatic-choosable if χl(G)=χ(G), chromatic-paintable if χp(G))=χ(G). By the characterizations of 2-choosable [ERT] and 2-paintable [Z] graphs, not all chromatic-choosable graphs are chromatic-paintable.
A graph G is elementary if E(G) can be 2-colored such that no induced subgraph of G isomorphic to P3 is monochromatic. (The family of elementary graphs includes the family of line graphs of bipartite graphs.)
Question 1: (Mahoney) If G is elementary and ω(G)≤3, then G is chromatic-choosable (and χ(G)=3) [GM1] (see also [GM2]). Do the same conditions imply that also G is chromatic-paintable?
Question 2: For any graph G, there exists n0 such that if n≥n0, then G∨Kn is chromatic-choosable [O]. Does the same statement hold for chromatic-paintability?
Question 3: Ohba's Conjecture [O] states that G is chromatic-choosable when |V(G)| ≤ 2 χ(G) + 1. Is it true that G is chromatic-paintable when |V(G)| ≤ 2 χ(G)? Also, Ohba's Conjecture is known to hold for complete multipartite graphs with independence number at most 5 [KSW]; are such graphs (with at most 2χ(G) vertices) chromatic-paintable?
Comments: Kim, Kwon, and Zhu [KKZ] added to the family of chromatic-choosable graphs that are not chromatic-paintable by showing for k>2 that the complete k-partite graph K3,2,2,2,2,…,2 is not k-paintable. Thus the paintability version of Ohba's Conjecture must be modified to forbid having 2χ(G)+1 vertices. They also gave an explicit strategy to show that graph K2,2,2,2,2,…,2 is k-paintable, which was proved earlier using the Combinatorial Nullstellensatz in [HWZ]. Ohba's Conjecture is similarly sharp in that a complete multipartite graph whose partite sets all have size 2 except for one of size 4 is not chromatic-choosable.
Ohba's Conjecture is known to hold when G has at most (5/3)χ(G)-(4/3) vertices. Also, for fixed ε, graphs with sufficiently many vertices that satisfy |V(G)|≤(2-ε)χ(G) are chromatic-choosable. One could analogously seek c such that if |V(G)|≤cχ(G), then G is chromatic-paintable.
Question 4: It is conjectured that claw-free graphs are chromatic-choosable [GM3]. If so, then are claw-free graphs also chromatic-paintable?
Question 5: Can the paintability ever exceed the choosability by more than 1?
Comments: Note that complete multipartite graphs have induced claws. It might be easier to study these questions first for 3-chromatic graphs. Proving that claw-free graphs are chromatic-paintable would be much stronger than the List Color Conjecture.
References:
[ERT]
P. Erdős, A.L. Rubin, H. Taylor. Choosability in graphs.
Proceedings of the West Coast Conference on Combinatorics, Graph Theory and
Computing (Humboldt State Univ., Arcata, Calif., 1979), pp. 125-157, Congress.
Numer., XXVI, Utilitas Math., Winnipeg, Man., 1980.
[GM1] S. Gravier and F. Maffray, Choice number of 3-colorable elementary
graphs. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166
(1997), 353-358.
[GM2] S. Gravier and F. Maffray, Graphs whose choice number is equal to their
chromatic number. J. Graph Theory 27 (1998), 87-97.
[GM3] S. Gravier and F. Maffray, On the choice number of claw-free perfect
graphs. 6th International Conference on Graph Theory. Discrete Math. 276
(2004), 211-218,
[HWZ] Po-Yi Huang, Tsai-Lien Wong, and Xuding Zhu, preprint.
[KKZ] S.-J. Kim, Y. Kwon, and X. Zhu,
On-line list colouring of complete multipartite graphs.
preprint.
[KSW] A. Kostochka, M Stiebitz, D. Woodall. Ohba's conjecture for graphs
with independence number five. Discrete Math. 311 (2001), 996-1005.
[O] K. Ohba. On Chromatic-Choosable Graphs. J. Graph Theory. 40: 130-135 (2002)
[S1] U. Schauz. Mr. Paint and Mrs. Correct. Electron. J.Combin. 16(1) (2009)
#R77.
[S2] U. Schauz. Flexible color lists in Alon and Tarsi's theorem, and time
scheduling with unreliable participants. Electron. J. Combin. 17 (2010) #R13
[Z] X. Zhu. On-Line List Colouring of Graphs. Electron. J. Combin. 16(1) (2009)
#R127.