-4
$\begingroup$

I can think of a way that to prove a 3-connected 5-regular planar graph does not contain a 5-critical subgraph.

We can choose two non-adjacent vertices a,b and contract them into a single vertex. If a and b has common neighbours, the resultant graph will still be a planar graph G'. But how can I prove chromatic number of G' is less or equal than 4?

Furthermore, how to prove that a 5-regular planar graph has chromatic number <= 4?

$\endgroup$

closed as off-topic by Kaveh, Kristoffer Arnsfelt Hansen, R B, Mohammad Al-Turkistany, Lev Reyzin Jul 25 '15 at 12:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Kristoffer Arnsfelt Hansen, R B, Mohammad Al-Turkistany, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ This is not quite a research-level question. $\endgroup$ – Yuval Filmus Mar 25 '14 at 3:36
  • 1
    $\begingroup$ It makes sense to me to ask for a short proof that every 5-regular planar graph is 4-colorable. All known proofs of 4CT use computers, including the proofs that follow after Appel, Koch and Haken's proof. The answerers who claim otherwise are mistaken. $\endgroup$ – user34834 Jul 19 '15 at 6:27
2
$\begingroup$

Every planar graph can be colored by 4 color, take dual of graph, the faces of dual are able to be colored by 4 color because of 4 color theorem, but they are also vertices of original graph.

$\endgroup$
  • $\begingroup$ But we need computers to prove 4-color thm, right? What I want is a human-doable proof to this weaker problem. $\endgroup$ – nuk Mar 25 '14 at 0:25
  • 1
    $\begingroup$ @nuk, We don't need to invent a wheel, 4 color theorem is a famous theorem and we don't need to prove it. But if you looking for non computer proof, take a look at seymour etal proof, here you can find a brief overview by one of a authors (Robin Thomas): people.math.gatech.edu/~thomas/FC/fourcolor.html $\endgroup$ – Saeed Mar 25 '14 at 1:01
  • 2
    $\begingroup$ As Tommy Jensen mentions below, even this second-generation proof of Robertson, Sanders, Seymour and Thomas uses computer verification, albeit a shorter a more trustworthy one. Recently Gonthier and his team came up with a completely formalized computer-aided proof, which should remove any doubts regarding the correctness of the previous proofs. Another computer-aided proof is due to John Steinberger: iiis.tsinghua.edu.cn/~john/4c.pdf. $\endgroup$ – Yuval Filmus Jul 19 '15 at 7:36

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