Research Article Open Access

Edge Double-Critical Graphs

John J. Lattanzio

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.

Journal of Mathematics and Statistics
Volume 6 No. 3, 2010, 357-358

DOI: https://doi.org/10.3844/jmssp.2010.357.358

Submitted On: 13 December 2009 Published On: 30 September 2010

How to Cite: Lattanzio, J. J. (2010). Edge Double-Critical Graphs. Journal of Mathematics and Statistics, 6(3), 357-358. https://doi.org/10.3844/jmssp.2010.357.358

  • 3,515 Views
  • 2,673 Downloads
  • 0 Citations

Download

Keywords

  • Chromatic number
  • critical clique
  • k-matching