Mycielski Graph

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

A Mycielski graph 👁 M_k
of order 👁 k
is a triangle-free graph with chromatic number 👁 k
having the smallest possible number of vertices. For example, triangle-free graphs with chromatic number 👁 k=4
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 👁 k
-Mycielski graph has vertex count

giving the sequence of vertex counts for 👁 n=1
, 2, ... are 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ... (OEIS A083329), and edge count

Mycielski graphs are implemented in the Wolfram Language as [[, 👁 {
, n]], and precomputed properties for small Mycielski graphs are implemented as [👁 {
, n👁 }
].

👁 M_k
is Hamilton-connected for all 👁 k
except 👁 k=3
(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 👁 R^3
, though ended up using a different graph on 31 vertices (the 31-de Grey graph).

The fractional chromatic number of the Mycielski graph 👁 M_n
is given by 👁 a_2=2
and

(Larsen et al. 1995), giving the sequence for 👁 n=2
, 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 👁 R^3
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

Mycielski Graph

Cite this as:

Weisstein, Eric W. "Mycielski Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MycielskiGraph.html

Subject classifications