By merging two-two color classes, the Four Color Theorem implies that every planar graph can be two-colored such that each color class induces a triangle-free graph. Is there a simpler proof for this fact?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Perhaps it's silly to ask, but conversely, could there be any hope to prove the FCT by finding and merging 2 suitable such triangle-free colorings? $\endgroup$– Yaakov BaruchCommented Dec 2, 2016 at 7:44
-
$\begingroup$ @Yaakov: What would be the use of triangle-free? I was thinking about something related earlier, but my hopes were crushed by this answer: mathoverflow.net/questions/255409/… $\endgroup$– domotorpCommented Dec 2, 2016 at 8:32
-
$\begingroup$ Interesting. Well, the devil is in the "suitable" of course. Given coloring A for ONE triangle, there are 4 non-uniform colorings B (out of 8) such that AB would give a different color to each vertex. So "suitable" would mean a second coloring where for each triangle the coloring comes from one of those 4 possibilities. I have have no idea of course how to find globally this second coloring. But I thought something like that might have been the inspiration for your question. $\endgroup$– Yaakov BaruchCommented Dec 2, 2016 at 11:15
-
1$\begingroup$ @Yaakov: Not at all, my motivation was that this paper uses only this corollary of the four color theorem, and so I wondered how difficult it is: arxiv.org/abs/1512.01953 $\endgroup$– domotorpCommented Dec 2, 2016 at 12:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Thomassen does indeed prove the vertex version, but in a different paper. In fact this paper proves the stronger statement that you can get a coloring without monochromatic triangles from any 2-list coloring.
A bit of googling revealed that originally the claim of the OP was proved in
Burstein M.I., "The bicolorability of planar hypergraphs", Sakharth. SSR Mecn. Akad. Moambe 78 (1975), no. 2, 293–296. (MR0396314)
This paper proves that for any planar triangulation, and any assignment of colors to the outer triangle which is not monochromatic one can extend the coloring to the entire triangulation while avoiding monochromatic triangles.
answered Dec 1, 2016 at 22:06
-
1$\begingroup$ By the way the proof of Burstein is fairly simple. For 4-connected triangulations, this is just a consequence of the fact that bridgeless cubic graphs have a perfect matching containing any given edge (since 2-colorings of planar triangulations without monochromatic faces are in 1-to-1 correspondence with perfect matchings of the dual graph). If the triangulation is not 4-connected, a simple induction finishes the proof by removing the interior of a separating triangle. $\endgroup$ Commented Dec 2, 2016 at 13:29
$\begingroup$
$\endgroup$
1
Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.
In fact it is so short that I'll give it in full:
Proof (by induction on $|V(G)|$). If $|V(G)|\le 4$ this holds by inspection so assume $|V(G)|\ge 5$.
Using induction, we can reduce the statement to the case where $G$ is 3-connected. So assume that $G$ is 3-connected. We claim that $G$ has a vertex $v$ which is not contained in any separating triangle. For, if $xyzx$ is a separating triangle in G such that $G - (x, y, z)$ has a component of smallest possible order, then no vertex in that component is contained in a separating triangle of $G$. Now consider any planar embedding of $G$. By the induction hypothesis, the edges of $G - v$ can be coloured in two colours such that no monochromatic triangle occurs. Now we colour the edges incident with $v$ in the same two colours such that no two consecutive edges are part of a monochromatic facial triangle. Then there is no monochromatic triangle at all and the proof is complete.
Added: Gordon has kindly pointed out that Carsten is colouring edges rather than vertices. So the original question is not yet answered.
answered Dec 1, 2016 at 7:15
-
3$\begingroup$ Is Carsten colouring edges? Is the OP colouring vertices? $\endgroup$ Commented Dec 1, 2016 at 8:05