Talk:Grötzsch's theorem

[Untitled]

I have given a short and efficient algorithmic proof of a theorem of Grötzsch that all triangle-free planar graphs are three colorable. Title of my paper is "A Short Proof of Groetzsch’s Three Color Theorem" and can be reached at: http://neu-tr.academia.edu/IbrahimCahit/Papers/1153722/A_Short_Proof_of_Groetzschs_Three_Color_Theorem

The article could use something about the complexity of finding these colorings so this is welcome news if true. But we should wait until it is reliably published in a refereed journal before adding it here, I think. —David Eppstein (talk) 08:46, 29 December 2011 (UTC)

Triangle-free planar graph?

It would be nice if the triangle-free planar graph was shown in planar form, like the drawing in this diagram: http://irem.univ-reunion.fr/IMG/jpg/colerr3.jpg Unfortunately, while the article of the graph in question (https://en.wikipedia.org/wiki/Bidiakis_cube) has both planar and coloured diagrams, it does not have a diagram which is both planar and coloured. As is, the diagram does not make it very clear that the graph in question is indeed planar. 2601:546:C300:8FF0:F5C5:5FE0:4A9A:9C99 (talk) 03:29, 12 July 2019 (UTC)

It's also not the best choice of graph because it has maximum degree three and so is also 3-colorable by Brooks' theorem regardless of triangles or planarity. —David Eppstein (talk) 06:05, 12 July 2019 (UTC)

I have drawn a new replacement image and added it to the article. —David Eppstein (talk) 21:04, 12 July 2019 (UTC)

It looks nice, is this just an arbitrary graph you made up? It does illustrate the idea better than the non-planar diagram that was there before, and also avoids the Brook's Theorem objection. (I am the original poster of this section). 2601:546:C300:8FF0:D5D6:32C3:E2A0:A52E (talk) 04:01, 14 July 2019 (UTC)

Sort-of-arbitrary. I made sure that it included both vertices of degree greater than three and odd cycles, and that it had no vertices of degree less than three, to make it less possible to prove 3-colorability through other standard results without going through this theorem. —David Eppstein (talk) 05:36, 14 July 2019 (UTC)