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).
