Kempe chain

Alfred B. Kempe(http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Kempe.htmlbio at St Andrews)first used these chains, now called after him,in 1879 in a “proof” of the four-color conjecture. Although Percy Heawoodfound a flaw in his proof 11 years later, the idea of Kempe chains itself isquite sound. Heawood used it to prove 5 colors suffice for maps on the plane,and the 1976 proof by Appel, Haken and Koch is also based on Kempe’s ideas.

The original Kempe chains were used in the context of colorings of countrieson a map, or in modern terminology face colorings of a plane graph $G$ (such that no two adjacent faces receive the same color). The idea wasextended by Heawood to embeddings of a graph in any other surface. Here

•
a Kempe chain of colors $a$ and $b$ is a maximal connected set of facesthat have either of those colors. as in: you can travel from any face in the set to any other, through the set. Maximal as in: there are no more faces of those colors you could enlarge the set with, i.e. that border the area you’ve already got.

In the modern dual formulation of the four-color theorem, faces of $G$ arereplaced by vertices of the dual graph $G^{*}$ (and vice versa); vertices areadjacent (linked by an edge) in $G^{*}$ whenever the corresponding faces of $G$ were adjacent (sharing a border). It now becomes a vertex coloringproblem (again, adjacent vertices must receive different colors). Here

•
a Kempe chain of colors $a$ and $b$ is a maximal connected subgraphcontaining only vertices of those colors. Connected as usual in graph theory(there’s a path between any two vertices) and maximal as in: there are nomore vertices of those colors you could enlarge the subgraph with, i.e. thatare adjacent to a vertex you’ve already got.
An alternative formulation: let $G(a,b)$ be the subgraph induced by all thevertices of color $a$ or $b$ (that is, with all the edges that run betweenthose vertices). Now any connected component $H(a,b)$ of $G(a,b)$ is a Kempechain.

While faces imply an embedding in a surface, the vertex version of thedefinition does not rely on any embedding. The chains are more useful inthe context of an embedding though.

Kempe chains of edges

With edge coloring of graphs (again, with different colors for adjacentedges i.e. those that meet at a vertex), an analogous concept can defined.Here

•
a Kempe chain of colors $a$ and $b$ is a maximal connected subgraphwhere the edges have either of those colors. Connected and maximal as before.
An alternative formulation: let $G(a,b)$ be the subgraph consisting of all theedges of color $a$ or $b$ (with any vertices incident to them). Now anyconnected component $H(a,b)$ of $G(a,b)$ is a Kempe chain.

While superficially similar to the previous definition, these “Kempe chains”are rather different animals. Their structure is far simpler. At any vertex of $H(a,b)$ , there can be at most one edge of color $a$ and one edge of color $b$ (at most two edges in all). Two things can happen:

$\\circ$
Every vertex in the chain has two such edges. In a finitegraph, this must mean a closed path (cycle). Note that, being coloredalternatingly, the number of edges must now be even.
$\\circ$
A vertex misses out on having an edge of one of those colors,and the chain stops there (it can’t miss out on both colors because thenit wouldn’t be part of the chain). In a finite graph, the other end ofthe chain must now also terminate somewhere (at a vertex that missesout either one of the colors). The chain is an open path of one ormore edges (its length can be even or odd).

Kempe chain arguments

One technique that can be used with all these types of chains is

•
swapping the colors in one $H(a,b)$ . This is always possible:by definition, there are no adjacent items that couldlead to a color clash.
Kempe slipped up when he swapped an $H(a,b)$ and an $H(a,c)$ withouttaking in account that swapping colors $a$ and $b$ in part of thegraph could alter the shape and connectedness of any $H(a,c)$ , butswapping colors in one Kempe chain at a time (and then taking stock ofthe lay of the land afresh) is quite safe.
Swapping can be used to free up a color somewhere, see thehttp://planetmath.org/node/6932proof of Vizing’s theorem for a repeated useof this ploy on edge-based Kempe chains.

Specific to the use in plane graphs we have that

•
if a Kempe chain forms a cycle, it disconnects the sphere or plane areainto disjoint parts (on the plane, inside and outside the cycle).

Specifically when four colors are used for faces:

•
The whole area is divided into red/green swathes and yellow/blue ones.Alternatively, into red/yellow and green/blue ones. Or red/blue andyellow/green ones.

Specifically for edge-based Kempe chains in regular $\\rho$ -valent graphs, ifwe try to edge-color the graph with only $\\rho$ colors:

•
No vertex can miss out on any of the $\\rho$ colors, so every $H(a,b)$ must be a cycle (of even length).

单词	KempeChain
释义	Kempe chain Alfred B. Kempe(http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Kempe.htmlbio at St Andrews)first used these chains, now called after him,in 1879 in a “proof” of the four-color conjecture. Although Percy Heawoodfound a flaw in his proof 11 years later, the idea of Kempe chains itself isquite sound. Heawood used it to prove 5 colors suffice for maps on the plane,and the 1976 proof by Appel, Haken and Koch is also based on Kempe’s ideas. The original Kempe chains were used in the context of colorings of countrieson a map, or in modern terminology face colorings of a plane graph $G$ (such that no two adjacent faces receive the same color). The idea wasextended by Heawood to embeddings of a graph in any other surface. Here • a Kempe chain of colors $a$ and $b$ is a maximal connected set of facesthat have either of those colors. as in: you can travel from any face in the set to any other, through the set. Maximal as in: there are no more faces of those colors you could enlarge the set with, i.e. that border the area you’ve already got. In the modern dual formulation of the four-color theorem, faces of $G$ arereplaced by vertices of the dual graph $G^{}$ (and vice versa); vertices areadjacent (linked by an edge) in $G^{}$ whenever the corresponding faces of $G$ were adjacent (sharing a border). It now becomes a vertex coloringproblem (again, adjacent vertices must receive different colors). Here • a Kempe chain of colors $a$ and $b$ is a maximal connected subgraphcontaining only vertices of those colors. Connected as usual in graph theory(there’s a path between any two vertices) and maximal as in: there are nomore vertices of those colors you could enlarge the subgraph with, i.e. thatare adjacent to a vertex you’ve already got. An alternative formulation: let $G(a,b)$ be the subgraph induced by all thevertices of color $a$ or $b$ (that is, with all the edges that run betweenthose vertices). Now any connected component $H(a,b)$ of $G(a,b)$ is a Kempechain. While faces imply an embedding in a surface, the vertex version of thedefinition does not rely on any embedding. The chains are more useful inthe context of an embedding though. Kempe chains of edges With edge coloring of graphs (again, with different colors for adjacentedges i.e. those that meet at a vertex), an analogous concept can defined.Here • a Kempe chain of colors $a$ and $b$ is a maximal connected subgraphwhere the edges have either of those colors. Connected and maximal as before. An alternative formulation: let $G(a,b)$ be the subgraph consisting of all theedges of color $a$ or $b$ (with any vertices incident to them). Now anyconnected component $H(a,b)$ of $G(a,b)$ is a Kempe chain. While superficially similar to the previous definition, these “Kempe chains”are rather different animals. Their structure is far simpler. At any vertex of $H(a,b)$ , there can be at most one edge of color $a$ and one edge of color $b$ (at most two edges in all). Two things can happen: $\\circ$ Every vertex in the chain has two such edges. In a finitegraph, this must mean a closed path (cycle). Note that, being coloredalternatingly, the number of edges must now be even. $\\circ$ A vertex misses out on having an edge of one of those colors,and the chain stops there (it can’t miss out on both colors because thenit wouldn’t be part of the chain). In a finite graph, the other end ofthe chain must now also terminate somewhere (at a vertex that missesout either one of the colors). The chain is an open path of one ormore edges (its length can be even or odd). Kempe chain arguments One technique that can be used with all these types of chains is • swapping the colors in one $H(a,b)$ . This is always possible:by definition, there are no adjacent items that couldlead to a color clash. Kempe slipped up when he swapped an $H(a,b)$ and an $H(a,c)$ withouttaking in account that swapping colors $a$ and $b$ in part of thegraph could alter the shape and connectedness of any $H(a,c)$ , butswapping colors in one Kempe chain at a time (and then taking stock ofthe lay of the land afresh) is quite safe. Swapping can be used to free up a color somewhere, see thehttp://planetmath.org/node/6932proof of Vizing’s theorem for a repeated useof this ploy on edge-based Kempe chains. Specific to the use in plane graphs we have that • if a Kempe chain forms a cycle, it disconnects the sphere or plane areainto disjoint parts (on the plane, inside and outside the cycle). Specifically when four colors are used for faces: • The whole area is divided into red/green swathes and yellow/blue ones.Alternatively, into red/yellow and green/blue ones. Or red/blue andyellow/green ones. Specifically for edge-based Kempe chains in regular $\\rho$ -valent graphs, ifwe try to edge-color the graph with only $\\rho$ colors: • No vertex can miss out on any of the $\\rho$ colors, so every $H(a,b)$ must be a cycle (of even length).
随便看	Universes and the univalence axiom Unknot unknot UnramifiedAction unramified action UnramifiedExtensionsAndClassNumberDivisibility unramified extensions and class number divisibility UnstableFixedPoint unstable fixed point UntouchableNumber untouchable number UnusualNumber unusual number UpcrossingsAndDowncrossings upcrossings and downcrossings UpperAndLowerBoundsToBinomialCoefficient upper and lower bounds to binomial coefficient UpperBound upper bound characterisation Characteristic characteristic CharacteristicallySimpleGroup characteristically simple group CharacteristicFunction