Originator(s): J.H. Folkman (communicated by Claude Tardif - REGS 2008)
Definitions: For a graph G, let k(G)=maxH⊆G{|V(H)|-2α(H)+2}. Let M(G) denote the graph obtained from a graph G by applying the Mycielski construction (add a copy ui of each vertex vi, plus edges joining each ui to NG(vi), and a final vertex w joined to each ui).
Background: Erdös and Hajnal [EH] conjectured that always χ(G)≤k(G). Folkman [F] proved this conjecture.
Problem: Characterize the graphs such that χ(G)=k(G). Call such graphs Folkman-sharp.
Comments: Folkman-sharp graphs include cycles, bipartite graphs, complete graphs, and M(G) when G is C5, bipartite, or complete. As a partial result, Tardif asked whether it always true that M(G) is Folkman-sharp when G is Folkman-sharp. During REGS 2008, it was proved that M(Cn) is Folkman-sharp for all n, but Ck∨Kr for k odd and at least 7 and r≥2 is a Folkman-sharp graph whose Mycielski graph is not Folkman-sharp.
Note that the Petersen graph is not Folkman-sharp, since it is 3-colorable but has 10 vertices and independence number 4. Also, M(Kn) illustrates that the maximum in the computation of k(G) need not be attained when H=G.
In addition, Folkman's proof of the bound involves "a sequence of some seventeen nontrivial lemmas". Is there an easier proof?
References:
[EH] P. Erdös and A. Hajnal; Problem 3, in Theory of Graphs (Proc. Coll.,
Tihany, 1966), p. 362, Academic Press, New York, 1968.
[F] Folkman, J. H.; An upper bound on the chromatic number of a graph.
Combinatorial theory and its application, II (Proc. Colloq., Balatonfüred,
1969), pp. 437--457. North-Holland, Amsterdam, 1970.