- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
Description
<jats:p>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 Erdős and Lovász. 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.</jats:p>
Journal
-
- The Electronic Journal of Combinatorics
-
The Electronic Journal of Combinatorics 17 2010-06-07
The Electronic Journal of Combinatorics
- Tweet
Details 詳細情報について
-
- CRID
- 1870865117762368384
-
- ISSN
- 10778926
-
- Data Source
-
- OpenAIRE