A Mycielski graph of order is a triangle-free graph with chromatic number having the smallest possible number of vertices. For example, triangle-free graphs with chromatic number include the Grötzsch graph (11 vertices), Chvátal graph (12 vertices), 13-cyclotomic graph (13 vertices), Clebsch graph (16 vertices), quartic vertex-transitive graph Qt49 (16 vertices), Brinkmann graph (21 vertices), Foster cage (30 vertices), Robertson-Wegner graph (30 vertices), and Wong graph (30 vertices). Of these, the smallest is the Grötzsch graph, which is therefore the Mycielski graph of order 4.
The first few Mycielski graphs are illustrated above and summarized in the table below.
The -Mycielski graph has vertex count
(1)
|
giving the sequence of vertex counts for , 2, ... are 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ... (OEIS A083329), and edge count
(2)
|
Mycielski graphs are implemented in the Wolfram Language as FromEntity[Entity["Graph", "Mycielski", n]], and precomputed properties for small Mycielski graphs are implemented as GraphData["Mycielski", n].
is Hamilton-connected for all except (Jarnicki et al. 2017).
The fractional chromatic number of the Mycielski graph is given by and
(3)
|
(Larsen et al. 1995), giving the sequence for , 3, ... of 2, 5/2, 29/10, 941/290, 969581/272890, ... (OEIS A073833 and A073834).