Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9516217 | Journal of Combinatorial Theory, Series B | 2005 | 11 Pages |
Abstract
Hajós' conjecture is false for almost all graphs but only few explicit counterexamples have appeared in the literature. We relate Hajós' conjecture to Ramsey theory, perfect graphs, and the maximum cut problem and obtain thereby new classes of explicit counterexamples. On the other hand, we show that some of the graphs which Catlin conjectured to be counterexamples to Hajós' conjecture satisfy the conjecture, and we characterize completely the graphs which satisfy Catlin's conjecture.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Carsten Thomassen,