[go: up one dir, main page]
TOPICS
Search

Mycielski Graph

DOWNLOAD Mathematica NotebookDownload 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.

MycielskiGraph

The first few Mycielski graphs are illustrated above and summarized in the table below.

kgraph
1singleton graph K_1
2path graph P_2
3cycle graph C_5
4Grötzsch graph

The k-Mycielski graph has vertex count

n(M_k)={1 for n=1; 3·2^(n-2)-1 for n>1,
(1)

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

m(M_k)=1/2(7·3^(n-2)+1)-3·2^(n-2).
(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}].

M_k is Hamilton-connected for all k except k=3 (Jarnicki et al. 2017).

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

a_n=a_(n-1)+a_(n-1)^(-1)
(3)

(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

Jarnicki, W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "Properties, Proved and Conjectured, of Keller, Mycielski, and Queen Graphs." To appear in Ars Math. Comtemp. 2017.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 Web Resource. https://mathworld.wolfram.com/MycielskiGraph.html

Subject classifications