Edge Double-Critical Graphs
Lattanzio · Journal of Mathematics and Statistics · 2010
Problem statement: The vertex double-critical conjecture that the only vertex doublecritical 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 doublecritical 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.