×

Mycielskians and matchings. (English) Zbl 1121.05047

Constructions of graphs with small clique number (largest number of vertices that are mutually adjacent) and (arbitrarily) large chromatic number has been an interesting area of investigation since the existence of such graphs is somewhat counterintuitive. In its generality this problem was solved by Erdős who showed that given any (arbitrarily large) \(t\) and \(m\), there exist graphs with no \(m\)-cycle and with chromatic number at least \(t\). In the special case \(m = 3\) such triangle-free graphs were shown to exist by Mycielski by an explicit recursive construction. This paper studies many interesting graph parameters such as regularity, matching and Hamiltonicity of the graphs obtained using Mycielski’s construction.

MSC:

05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link