Journal of Mathematics and Statistics | |
Edge Double-Critical Graphs | Science Publications | |
John J. Lattanzio1  | |
关键词: 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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201912010160503ZK.pdf | 35KB | download |