Kempe chain: Difference between revisions
Vstephen B (talk | contribs) |
|||
| (32 intermediate revisions by 22 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Mathematical device used in proof of the four colour theorem}} |
|||
[[File:Kempe Chain.png|thumb|A graph containing a Kempe chain consisting of alternating blue and red vertices]] |
|||
In [[mathematics]], a '''Kempe chain''' is a device used mainly in the study of the [[four colour theorem]]. Intuitively, it is a connected chain of vertices on a [[graph (discrete mathematics)|graph]] with alternating colours. |
|||
== |
==History== |
||
Kempe chains were first used by [[Alfred Kempe]] in his attempted [[mathematical proof|proof]] of the four colour theorem.<ref name="AMS"> |
|||
{{cite web |url=http://www.ams.org/publicoutreach/feature-column/fcarc-coloring5 |title=Colorful Mathematics: Part I |author=<!--Not stated--> |date= |website=American Mathematical Society |access-date=July 10, 2020}}</ref> Even though his proof turned out to be incomplete, the method of Kempe chains is crucial to the success of valid modern proofs, such as the first successful one by [[Kenneth Appel]] and [[Wolfgang Haken]].<ref>{{Cite journal |last1=Appel |first1=K. |last2=Haken |first2=W. |date=1977-09-01 |title=Every planar map is four colorable. Part I: Discharging |journal=Illinois Journal of Mathematics |volume=21 |issue=3 |doi=10.1215/ijm/1256049011 |issn=0019-2082|doi-access=free }}</ref><ref>{{Cite journal |last1=Robertson |first1=Neil |last2=Sanders |first2=Daniel |last3=Seymour |first3=Paul |last4=Thomas |first4=Robin |date=1997-05-01 |title=The Four-Colour Theorem |journal=Journal of Combinatorial Theory, Series B |volume=70 |issue=1 |pages=2–44 |doi=10.1006/jctb.1997.1750 |issn=0095-8956|doi-access=free }}</ref> Furthermore, the method is used in the proof of the [[five color theorem]] by [[Percy John Heawood]], a weaker but more easily proven version of the four colour theorem.<ref name="AMS"/> |
|||
| ⚫ | |||
| ⚫ | |||
The term "Kempe chain" is used in two different but related ways. |
The term "Kempe chain" is used in two different but related ways. |
||
Suppose ''G'' is a [[ |
Suppose ''G'' is a [[graph (discrete mathematics)|graph]] with [[vertex (graph theory)|vertex]] set ''V'', with a given colouring function |
||
: <math>c : V \to S</math> |
: <math>c : V \to S,</math> |
||
where ''S'' is a finite set of colours, containing at least two distinct colours ''a'' and ''b''. If ''v'' is a vertex with colour ''a'', then the (''a'', ''b'')-Kempe chain of ''G'' containing ''v'' is the maximal connected subset of ''V'' which contains ''v'' and whose vertices are all coloured either ''a'' or ''b''. |
where ''S'' is a finite set of colours, containing at least two distinct colours ''a'' and ''b''. If ''v'' is a vertex with colour ''a'', then the (''a'', ''b'')-Kempe chain of ''G'' containing ''v'' is the maximal connected subset of ''V'' which contains ''v'' and whose vertices are all coloured either ''a'' or ''b''. |
||
The above definition is what Kempe worked with. Typically the set ''S'' has four elements (the four colours of the four colour theorem), and ''c'' is a [[proper colouring]], that is, each pair of adjacent vertices in ''V'' are assigned distinct colours. |
The above definition is what Kempe worked with. Typically, the set ''S'' has four elements (the four colours of the four colour theorem), and ''c'' is a [[proper coloring|proper colouring]], that is, each pair of adjacent vertices in ''V'' are assigned distinct colours. With these additional conditions, ''a'' and ''b'' are two out of the four colours available, and every element of the (''a'', ''b'')-Kempe chain has neighbours in the chain of only the other colour. |
||
A more general definition, which is used in the modern computer-based proofs of the four colour theorem, is the following. Suppose again that ''G'' is a graph, with edge set ''E'', and this time we have a colouring function |
A more general definition, which is used in the modern computer-based proofs of the four colour theorem, is the following. Suppose again that ''G'' is a graph, with edge set ''E'', and this time we have a colouring function |
||
| Line 20: | Line 21: | ||
This second definition is typically applied where ''S'' has three elements, say ''a'', ''b'' and ''c'', and where ''V'' is a [[cubic graph]], that is, every vertex has three incident edges. If such a graph is properly coloured, then each vertex must have edges of three distinct colours, and Kempe chains end up being [[path (graph theory)|path]]s, which is simpler than in the case of the first definition. |
This second definition is typically applied where ''S'' has three elements, say ''a'', ''b'' and ''c'', and where ''V'' is a [[cubic graph]], that is, every vertex has three incident edges. If such a graph is properly coloured, then each vertex must have edges of three distinct colours, and Kempe chains end up being [[path (graph theory)|path]]s, which is simpler than in the case of the first definition. |
||
| ⚫ | |||
| ⚫ | |||
{{Expand |
{{Expand section|date=June 2008}} |
||
<!-- here we need a pretty picture and a down-to-earth explanation NOT in terms of graph theory terminology --> |
<!-- here we need a pretty picture and a down-to-earth explanation NOT in terms of graph theory terminology --> |
||
== |
==Application to the four colour theorem== |
||
{{main| Four color theorem}} |
|||
{{Expand-section|date=June 2008}} |
|||
<!-- Here we need an explanation of e.g. how Kempe chains can be used to reduce a vertex of degree four in the 4ct case, and how to reduce a vertex of degree 5 in the 5ct case, again with some pretty pictures --> |
<!-- Here we need an explanation of e.g. how Kempe chains can be used to reduce a vertex of degree four in the 4ct case, and how to reduce a vertex of degree 5 in the 5ct case, again with some pretty pictures --> |
||
In the four colour theorem, Kempe was able to prove that all graphs necessarily have a vertex of five or less, or containing a vertex that touches five other vertices, called its [[Neighbourhood (graph theory)|neighbours]]. As such, to prove the four colour theorem, it is sufficient to prove that vertices of five or less were all four-colourable. Kempe was able to prove the case of degree four and give a partial proof of degree five using Kempe chains.<ref>Appel, Kenneth; Haken, Wolfgang (1989), Every Planar Map is Four-Colorable, Contemporary Mathematics, 98, With the collaboration of J. Koch., Providence, RI: American Mathematical Society, doi:10.1090/conm/098, {{ISBN|0-8218-5103-9}}, MR 1025335</ref> |
|||
In this case, Kempe chains are used to prove the idea that no vertex of degree four has to be touching four distinct colours different from itself. First, one can create a graph with a vertex ''v'' and four vertices as neighbours. If we remove the vertex ''v'', we can four-colour the remaining vertices. We can set the colours as (in clockwise order) red, yellow, blue, and green. In this situation, there can be a Kempe chain joining the red and blue neighbours or a Kempe chain joining the green and yellow neighbours, but not both, since these two paths would necessarily intersect, and the vertex where they intersect cannot be coloured with both red or blue and with green or yellow at the same time. Supposing that the Kempe chain is connecting the green and yellow neighbours, red and blue must then necessarily not have a Kempe chain between them. So, when placing the original vertex ''v'' back into the graph, we can simply reverse the colours of the red vertex and its neighbours (including the red vertex, making it blue), which leaves vertex ''v'' with two blue neighbours, one green, and one yellow. This means ''v'' has only three distinct colours as neighbours, and that we can now colour vertex ''v'' as red. This results in a four-coloured graph.<ref>Kempe, A. B. (1879), "On the Geographical Problem of the Four Colours", American Journal of Mathematics, The Johns Hopkins University Press, 2 (3): 193–220</ref> |
|||
==Other applications== |
|||
Kempe chains have been used to solve problems in ''colouring extension''.<ref>{{Cite journal | doi = 10.1006/jctb.1998.1827| title = You Can't Paint Yourself into a Corner| journal = Journal of Combinatorial Theory, Series B| volume = 73| issue = 2| pages = 189–194| year = 1998| last1 = Albertson | first1 = M. O. | doi-access = free}}</ref><ref>{{Cite journal | doi = 10.1006/jctb.1999.1913| title = Extending Graph Colorings| journal = Journal of Combinatorial Theory, Series B| volume = 77| pages = 83–95| year = 1999| last1 = Albertson | first1 = M. O. | last2 = Moore | first2 = E. H. | doi-access = free}}</ref> Kempe chains can be used for [[register allocation]].{{Citation needed|date=April 2024}} |
|||
== See also == |
|||
* [[Four color theorem|Four colour theorem]] |
|||
* [[Five color theorem|Five colour theorem]] |
|||
* [[Graph coloring|Graph colouring]] |
|||
==References== |
|||
{{reflist}} |
|||
{{DEFAULTSORT:Kempe Chain}} |
|||
[[Category:Graph |
[[Category:Graph coloring]] |
||
Latest revision as of 00:59, 29 August 2024
In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem. Intuitively, it is a connected chain of vertices on a graph with alternating colours.
History
[edit]Kempe chains were first used by Alfred Kempe in his attempted proof of the four colour theorem.[1] Even though his proof turned out to be incomplete, the method of Kempe chains is crucial to the success of valid modern proofs, such as the first successful one by Kenneth Appel and Wolfgang Haken.[2][3] Furthermore, the method is used in the proof of the five color theorem by Percy John Heawood, a weaker but more easily proven version of the four colour theorem.[1]
Formal definition
[edit]The term "Kempe chain" is used in two different but related ways.
Suppose G is a graph with vertex set V, with a given colouring function
where S is a finite set of colours, containing at least two distinct colours a and b. If v is a vertex with colour a, then the (a, b)-Kempe chain of G containing v is the maximal connected subset of V which contains v and whose vertices are all coloured either a or b.
The above definition is what Kempe worked with. Typically, the set S has four elements (the four colours of the four colour theorem), and c is a proper colouring, that is, each pair of adjacent vertices in V are assigned distinct colours. With these additional conditions, a and b are two out of the four colours available, and every element of the (a, b)-Kempe chain has neighbours in the chain of only the other colour.
A more general definition, which is used in the modern computer-based proofs of the four colour theorem, is the following. Suppose again that G is a graph, with edge set E, and this time we have a colouring function
If e is an edge assigned colour a, then the (a, b)-Kempe chain of G containing e is the maximal connected subset of E which contains e and whose edges are all coloured either a or b.
This second definition is typically applied where S has three elements, say a, b and c, and where V is a cubic graph, that is, every vertex has three incident edges. If such a graph is properly coloured, then each vertex must have edges of three distinct colours, and Kempe chains end up being paths, which is simpler than in the case of the first definition.
In terms of maps
[edit]![[icon]](/enwiki/wiki/File:Wiki_letter_w_cropped.svg){kind=small} | This section needs expansion. You can help by adding to it. (June 2008) |
Application to the four colour theorem
[edit]In the four colour theorem, Kempe was able to prove that all graphs necessarily have a vertex of five or less, or containing a vertex that touches five other vertices, called its neighbours. As such, to prove the four colour theorem, it is sufficient to prove that vertices of five or less were all four-colourable. Kempe was able to prove the case of degree four and give a partial proof of degree five using Kempe chains.[4]
In this case, Kempe chains are used to prove the idea that no vertex of degree four has to be touching four distinct colours different from itself. First, one can create a graph with a vertex v and four vertices as neighbours. If we remove the vertex v, we can four-colour the remaining vertices. We can set the colours as (in clockwise order) red, yellow, blue, and green. In this situation, there can be a Kempe chain joining the red and blue neighbours or a Kempe chain joining the green and yellow neighbours, but not both, since these two paths would necessarily intersect, and the vertex where they intersect cannot be coloured with both red or blue and with green or yellow at the same time. Supposing that the Kempe chain is connecting the green and yellow neighbours, red and blue must then necessarily not have a Kempe chain between them. So, when placing the original vertex v back into the graph, we can simply reverse the colours of the red vertex and its neighbours (including the red vertex, making it blue), which leaves vertex v with two blue neighbours, one green, and one yellow. This means v has only three distinct colours as neighbours, and that we can now colour vertex v as red. This results in a four-coloured graph.[5]
Other applications
[edit]Kempe chains have been used to solve problems in colouring extension.[6][7] Kempe chains can be used for register allocation.[citation needed]
See also
[edit]References
[edit]- ^ a b "Colorful Mathematics: Part I". American Mathematical Society. Retrieved July 10, 2020.
- ^ Appel, K.; Haken, W. (1977-09-01). "Every planar map is four colorable. Part I: Discharging". Illinois Journal of Mathematics. 21 (3). doi:10.1215/ijm/1256049011. ISSN 0019-2082.
- ^ Robertson, Neil; Sanders, Daniel; Seymour, Paul; Thomas, Robin (1997-05-01). "The Four-Colour Theorem". Journal of Combinatorial Theory, Series B. 70 (1): 2–44. doi:10.1006/jctb.1997.1750. ISSN 0095-8956.
- ^ Appel, Kenneth; Haken, Wolfgang (1989), Every Planar Map is Four-Colorable, Contemporary Mathematics, 98, With the collaboration of J. Koch., Providence, RI: American Mathematical Society, doi:10.1090/conm/098, ISBN 0-8218-5103-9, MR 1025335
- ^ Kempe, A. B. (1879), "On the Geographical Problem of the Four Colours", American Journal of Mathematics, The Johns Hopkins University Press, 2 (3): 193–220
- ^ Albertson, M. O. (1998). "You Can't Paint Yourself into a Corner". Journal of Combinatorial Theory, Series B. 73 (2): 189–194. doi:10.1006/jctb.1998.1827.
- ^ Albertson, M. O.; Moore, E. H. (1999). "Extending Graph Colorings". Journal of Combinatorial Theory, Series B. 77: 83–95. doi:10.1006/jctb.1999.1913.