Autor: |
James Tilley |
Jazyk: |
angličtina |
Rok vydání: |
2018 |
Předmět: |
|
Zdroj: |
Mathematics, Vol 6, Iss 12, p 309 (2018) |
Druh dokumentu: |
article |
ISSN: |
2227-7390 |
DOI: |
10.3390/math6120309 |
Popis: |
The 4-color theorem was proved by showing that a minimum counterexample cannot exist. Birkhoff demonstrated that a minimum counterexample must be internally 6-connected. We show that a minimum counterexample must also satisfy a coloring property that we call Kempe-locking. The novel idea explored in this article is that the connectivity and coloring properties are incompatible. We describe a methodology for analyzing whether an arbitrary planar triangulation is Kempe-locked. We provide a heuristic argument that a fundamental Kempe-locking configuration must be of low order and then perform a systematic search through isomorphism classes for such configurations. All Kempe-locked triangulations that we discovered have two features in common: (1) they are Kempe-locked with respect to only a single edge, say x y , and (2) they have a Birkhoff diamond with endpoints x and y as a subgraph. On the strength of our investigations, we formulate a plausible conjecture that the Birkhoff diamond is the only fundamental Kempe-locking configuration. If true, this would establish that the connectivity and coloring properties of a minimum counterexample are indeed incompatible. It would also imply the appealing conclusion that the Birkhoff diamond configuration alone is responsible for the 4-colorability of planar triangulations. |
Databáze: |
Directory of Open Access Journals |
Externí odkaz: |
|
Nepřihlášeným uživatelům se plný text nezobrazuje |
K zobrazení výsledku je třeba se přihlásit.
|