To my knowledge these problems are open. If you have remarks, correction or solution ... send email to yared@math.ohio-state.edu
1. Generalizing Grotzsch's Theorem:
MOTIVE: Why do we like Grotzsch's Theorem? Because it is provable in less than 3 pages. Thanks to Thomassen. Of course also because the 4-Color-Theorem is not (so far) provable by hand!! Grotzsch theorem in a way says "well the proof of 4-Color-Theorem may be inaccessible to human unless aided by machine, but take out the triangle and I can give you a better result, the 3-Color-Theorem! What is yet amazing is as the proof has become short, so did the algorithm to color triangle-free planar graphs. In general, minimally coloring planar graphs is "NP-complete" (The mysterious problem class known as NPC). The known algorithms to solve problems in NPC are extremely slow (deterministically). However, when we avoid triangles from the plane, the coloring problem becomes polynomial time solvable (that means fast). Now, can we search for an analogous theorem for the general case? Hadwiger in 1943 generalized the 4-Color-Conjecture to a much larger set of graphs. His conjecture remains open to date and it is one of (if not THE) most interesting open question in graph theory. Clearly it is hard, since the special case, which is 4-Color-Theorem is already very very hard. BUT can one search for generalized Grotzsch's theorem that gives a nice support to Hadwiger? ----------------------------------
I posted the problem listed as number 4 below a while ago. (Now already solved, see publication list #2 ). Hence we know triangle-free graphs with no K_5 minor are 3-colorable. Robin Thomas conjectured a few years ago that triangle-free graphs with no K_6 are 4-colorable. The conjecture is still open. Assuming this conjecture holds, is it true in general triangle-free graphs with no K_k minor are k-2-colorable (if k>4)? In fact we first asked a stronger condition. Does K_{k-2}-free imply k-2-colorable? But found a nice counterexample to this. You can construct a 5-chromatic, K4-free graph with no K6-minor using the odd wheel W5 and six more vertices. (See page 17 of the paper by Naserasr, YN, Skrekovski, of publication list in my webpage)
2. (Conjecture of Naserasr, YN and Skrekovski) Every K6-minor-free graph of girth at least five is 3 colorable. (Notes: First known graph of girth 4, with no K6-minor (with a stronger property that it is an apex graph) and 4-chromatic is due to Donovan Hare. We believe the 4 cycles play a key role in making a fourth color necessary.
3. Submitted to Mid-Summer Combinatorial Workshop, 2003 Prague
4. (this is already solved by Reza Naserasr, Riste Skrekovski and YN, a more general question has arisen from it in our ) A beautiful theorem in graph theory (Grotzsch's Theorem) states that planar graphs with no triangle can be colored using only 3 colors. Are triangle-free graphs with no K5-minor also 3-colorable? Just as the 4-color-theorem is generalized to K5-minor-free graphs, has anyone generalized Grotzsch's Theorem as well? Or does there exist a counterexample?
5. Are triangle-free, pentagon-free planar graphs 8/3-colorable? It suffices to answer this question for planar graphs of girth 7.
6. One can find a unique K4-minor free graph we call "3-pentagon" (See "minimal universal and dense minor closed classes" paper of Nesetril and YN) such that any K4-minor-free graph not containing 3-pentagon is homomorphically equivalent to its shortest odd cycle. Does there exist an analogous theorem for planar graphs (or K5-minor-free graphs)? In other words, does there exist a finite set S of graphs in the class such that any planar graph forbidding the graphs of S as minors is forced to be equivalent to its shortest odd cycle? (to avoid triviality, one should assume K5 and K3,3 are already in S and the graphs in S are homomorphically incomparable)
7. A class C together with an order "\leq" is said to be universal if every countable partial order (P, \leq_p) can be injectively embedded in C. Does there exist a class C which has an infinite anti-chain and a dense subset that is not universal? Note that, if C is universal then it should certainly have an infinite anti-chain and a dense subset. For otherwise, there are Po-sets containing infinite anti-chains or dense and so these classes would not be embeddable in C. So I am asking if universality is equivalent to these two properties "density" and existence of an infinite anti-chain. See the paper mentioned in 4. for some basic definitions.