mathworld.wolfram.com

Mycielski Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
  • ️Sun Dec 23 2001
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

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.

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