Edge Double-Critical Graphs | Science Publications

Journal of Mathematics and Statistics

John J. Lattanzio¹ 

关键词: Chromatic number;    critical clique;    k-matching;   

DOI  :  10.3844/jmssp.2010.357.358

学科分类：社会科学、人文和艺术（综合）

来源: Science Publications

【 摘 要 】

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.

【 授权许可】

Unknown