科研之友
微信
新浪微博
Facebook
分享链接
摘要
A connected k-chromatic graph G is double-critical if for all edges uv of G the graph G - u - v is (k - 2)-colourable. The only known double-critical k-chromatic graph is the complete k-graph K(k). The conjecture that there are no other double-critical graphs is a special case of a conjecture from 1966, due to Erdos and Lovasz. The conjecture has been verified for k at most 5. We prove for k = 6 and k = 7 that any non-complete double-critical k-chromatic graph is 6-connected and contains a complete k-graph as a minor.
- 出版日期2010-6-7
