Isomorphic Factorization

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

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

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

Some Ramsey numbers have been bounded via isomorphic factorizations. For instance, the complete graph  has the Clebsch graph as a factor, proving  (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,  was proven.)

In addition,  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  via another 7-split is an unsolved problem.

---

REFERENCES

Farrugia, A. "Self-complementary Graphs and Generalizations: A Comprehensive Reference Manual." Masters Thesis. University of Malta, 1999. http://members.lycos.co.uk/afarrugia/sc-graph/sc-graph-survey.ps.

Gardner, 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 ." http://www.math.uiuc.edu/~west/openp/hoffsing.html.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength