Journal of Mathematics and Statistics

Edge Double-Critical Graphs

John J. Lattanzio

DOI : 10.3844/jmssp.2010.357.358

Journal of Mathematics and Statistics

Volume 6, Issue 3

Pages 357-358

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.

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.