Edge Double-Critical Graphs
Abstract
Problem statement: The vertex double-critical conjecture that the only vertex double-critical graph is the complete graph has remained unresolved for over forty years. The edge analogue of this conjecture has been proved. Approach: It was observed that if the chromatic number decreases by two upon the removal of a 2-matching, then the 2-matching comprises four vertices which determine an induced subgraph isomorphic to the complete graph on four vertices. This observation was generalized to t-matchings. Results: In this note, it has been shown that the only edge double-critical graph is the complete graph. Conclusion/Recommendations: An alternate proof that the only edge double-critical graph is the complete graph has been obtained. Moreover, the result has been obtained independently.
DOI: https://doi.org/10.3844/jmssp.2010.357.358
Copyright: © 2010 John J. Lattanzio. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,514 Views
- 2,673 Downloads
- 0 Citations
Download
Keywords
- Chromatic number
- critical clique
- k-matching