0
$\begingroup$

can the following proposition be proved? If so please suggest a method. Can Kempe’s Argument be used for proof ?
Proposition: A normal map has a colouring of countries by 4 colours iff the edges of the map can be properly coloured by 3 colours.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

This was proven already in the $19^{\rm th}$ century. In the following paper it is shown that the "eessentially different" $3$-colorings of the edges are in one-one correspondence with the "essentially different" $4$-colorings of the countries:

http://retro.seals.ch/digbib/view?rid=ensmat-001:1965:11::337&id=browse&id2=browse5&id3=1

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! But the proof seems too complex for me. I'm a beginner in Graph theory and am incapable of understanding the proof. $\endgroup$
    – Riyafa Abdul Hameed
    Oct 10, 2014 at 17:31
0
$\begingroup$

I have found a proper proof in these places:

1) Peterson Graph by D.A. Holton & J. Sheehan

2) http://www.cs.rpi.edu/~goldberg/14-GT/18-plane.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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