A connected $k$-chromatic graph $G$ is said to be double-critical if for all edges $uv$ of $G$ the graph $G - u - v$ is $(k-2)$-colourable. A longstanding conjecture of Erd?s and Lovász states that the complete graphs are the only double-critical graphs. Kawarabayashi, Pedersen and Toft [Electron. J. Combin., 17(1): Research Paper 87, 2010] proved that every double-critical $k$-chromatic graph with $k leq 7$ contains a $K_k$ minor. It remains unknown whether an arbitrary double-critical $8$-chromatic graph contains a $K_8$ minor, but in this paper we prove that any double-critical $8$-chromatic contains a minor isomorphic to $K_8$ with at most one edge missing. In addition, we observe that any double-critical $8$-chromatic graph with minimum degree different from $10$ and $11$ contains a $K_8$ minor.
展开▼
机译：如果对于$ G $的所有边$ uv $，图$ G-u-v $是可着色的（k-2）$色，则连通的$ k $色图$ G $被认为是双临界的。 Erd？s和Lovász的一个长期推测认为，完整的图是唯一的双临界图。 Kawarabayashi，Pedersen和Toft [电子。 J. Combin。，17（1）：研究论文87，2010]证明，每个带有$ k leq 7 $的双临界$ k $-色图都包含$ K_k $次要。任意一个双临界的$ 8 $色图是否包含$ K_8 $次要色仍是未知的，但是在本文中，我们证明了任何双临界的$ 8 $色图都包含了与$ K_8 $的次要同构，最多缺少一个边。另外，我们观察到任何最小程度不同于$ 10 $和$ 11 $的双临界$ 8 $色图都包含$ K_8 $小数。
展开▼
