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).
de Grey (2026) constructed a unit-distance embedding of the 4-Mycielski (Grötzsch graph) in three dimensions and attempted
to construct one for the 5-Mycielski graph in his construction of 5-chromatic, triangle-free, unit-distance
graph in 
,
though ended up using a different graph on 31 vertices (the 31-de
Grey graph).
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).
See also
Grötzsch Graph, Triangle-Free Graph
Explore with Wolfram|Alpha
References
de Grey, A. D. N. J. "A 5-Chromatic, Triangle-Free Unit-Distance Graph in 
With 61 Vertices." Geombinatorics 35,
2026.Jarnicki, W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "Properties,
Proved and Conjectured, of Keller, Mycielski, and Queen Graphs." 25 Jun 2016.
https://arxiv.org/abs/1606.07918.Larsen,
M.; Propp, J.; and Ullman, D. "The Fractional Chromatic Number of Mycielski's
Graphs." J. Graph Th. 19, 411-416, 1995.Mycielski,
J. "Sur le coloriage des graphes." Colloq. Math. 3, 161-162,
1955.Sloane, N. J. A. Sequences A073833,
A073834, and A083329
in "The On-Line Encyclopedia of Integer Sequences."Soifer,
A. The
Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its
Creators. New York: Springer, pp. 85-86, 2008.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Mycielski Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MycielskiGraph.html