Let $xy$ be an edge in a planar triangulation $T$ that is at least 4-connected and let $uxvy$ be the 4-cycle delineating the 4-face of the near-triangulation $G_{xy}$ obtained by deleting $xy$ from $T$; $T$ is said to be Kempe-locked with respect to $xy$ if there are exactly three Kempe chains including both $x$ and $y$ in every 4-coloring of $G_{xy}$ in which $x$ and $y$ have the same color. If $xy$ is a Kempe-locked edge in $T$, the proper subgraph $K_{xy}$ of $G_{xy}$ obtained by deleting $u$ and $v$ (and their incident edges) is said to be the Kempe-locking configuration for that edge; a Kempe-locking configuration is said to be fundamental if it contains no smaller Kempe-locking configuration as a proper subgraph. The Birkhoff diamond of order 10 is the lowest-order fundamental Kempe-locking configuration and it might be the only fundamental Kempe-locking configuration. Any ideas on how that could be proved? I have checked all isomorphism classes of 4-connected triangulations through order 17 and all isomorphism classes of 5-connected triangulations through order 24 and have found no other fundamental Kempe-locking configurations.
Add a comment
|