14
$\begingroup$

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?

$\endgroup$
  • $\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 Baruch Dec 2 '16 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$ – domotorp Dec 2 '16 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 Baruch Dec 2 '16 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$ – domotorp Dec 2 '16 at 12:00
7
$\begingroup$

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.

$\endgroup$
  • 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$ – Louis Esperet Dec 2 '16 at 13:29
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Is Carsten colouring edges? Is the OP colouring vertices? $\endgroup$ – Gordon Royle Dec 1 '16 at 8:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.