Kempe chain


Also found in: Wikipedia.

Kempe chain

[′kem·pə ‚chān]
(mathematics)
A subgraph of a graph whose vertices have been colored, consisting of vertices which have been assigned a given color or colors and arcs connecting pairs of such vertices.
References in periodicals archive ?
A path contained within is termed a Kempe chain [WT72], so-named in honor of the foundational work done on them by Kempe [Kem79].
If a and b belong to the same connected component of , then they are connected by some Kempe chain Pj contained within [c.sub.ij].
It follows that [v.sub.i] and [v.sub.i] are the endpoints of a Kempe chain contained within ([v.sub.i]).
From the proof of Lemma 8, we know that u and v are the endpoints of a Kempe chain containing [v.sub.i].
Although the immersion order is traditionally defined in terms of taking subgraphs and lifting pairs of edges, the fact that different Kempe chains are edge-disjoint make it helpful for us to utilize the following alternate characterization: H is immersed in G if and only if there exists an injection from the vertices of The conjecture was first published in the preliminary conference version of this paper at COCOON 2003.
Kempe chains play a pivotal role in our investigation.
The use of Kempe chains in Lemma 6 has been especially effective, so much so that we need only paths not chains in what follows.