Skip to main content
MathOverflow

Return to Question

added 67 characters in body
Source Link
Jim Tilley
Jim Tilley
  • 91
  • 2

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-lockedKempe-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. TheIf $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 for the edge $xy$ in $T$. It is said to be fundamentalfundamental 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.

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. 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 the edge $xy$ in $T$. It 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.

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.

Source Link
Jim Tilley
Jim Tilley
  • 91
  • 2

Finding fundamental Kempe-locking configurations

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. 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 the edge $xy$ in $T$. It 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.