Došlić, Tomislav Mycielskians and matchings. (English) Zbl 1121.05047 Discuss. Math., Graph Theory 25, No. 3, 261-266 (2005). 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. Reviewer: Sharad Sane (Mumbai) Cited in 6 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C12 Distance in graphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:Chromatic number; clique number; Mycielski graphs; matchings PDFBibTeX XMLCite \textit{T. Došlić}, Discuss. Math., Graph Theory 25, No. 3, 261--266 (2005; Zbl 1121.05047) Full Text: DOI Link