Isomorphic Factorization

Isomorphic factorization colors the edges a given graph G with k colors so that the colored subgraphs are isomorphic. The graph G is then k-splittable, with k as the divisor, and the subgraph as the factor.

When a complete graph is 2-split, a self-complementary graph results. Similarly, an n-regular class 1 graph can be n-split into graphs consisting of disconnected edges, making n the edge chromatic number.

The complete graph K_9 can be 3-split into identical planar graphs.

Some Ramsey numbers have been bounded via isomorphic factorizations. For instance, the complete graph K_(16) has the Clebsch graph as a factor, proving R(3,3,3)>16 (Gardner 1989). That is, the complete graph on 16 points can be three-colored so that no triangle of a single color appears. (In 1955, R(3,3,3)=17 was proven.)


In addition, K_(16) can be 8-split with the Petersen graph as a factor, or 5-split with a doubled cubical graph as a factor (shown by Exoo in 2005).

The Hoffman-Singleton graph is 7-splittable into edges (shown by Royle in 2004). Whether the Hoffman-Singleton graph is a factor of K_(50) via another 7-split is an unsolved problem.

See also

Complete Graph, Edge Coloring, Isomorphic Graphs

This entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha


Farrugia, A. "Self-complementary Graphs and Generalizations: A Comprehensive Reference Manual." Masters Thesis. University of Malta, 1999., M. "Ramsey Theory." Ch. 17 in Penrose Tiles and Trapdoor Ciphers... and the Return of Dr. Matrix, reissue ed. New York: W. H. Freeman, pp. 231-247, 1989.West, D. "Hoffman-Singleton Decomposition of K_(50)."

Referenced on Wolfram|Alpha

Isomorphic Factorization

Cite this as:

Pegg, Ed Jr. "Isomorphic Factorization." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications