Article ID Journal Published Year Pages File Type
9516217 Journal of Combinatorial Theory, Series B 2005 11 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,