Clique Partitions of Graphs

Grant Zhang

Department of Mathematical Sciences
University of Alabama in Huntsville

April 5, 1996

Abstract

A complete subgraph of G is called a clique of G. A collection C of cliques of G is a clique partition if every edge of G is contained in exactly one member of C. A clique partition is minimum if its cardinality is least among all clique partitions of G. The clique partition number is G, cp(G), is the cardinality of a minimum clique partition.

The talk discusses the problem of determining cp(G). The problem is closely related to many problems in block designs. Equivalent formulations in terms of set intersections and matrix decompositions will be given. Other related problems will be considered.