2008/04/16 by Tao-Ming Wang, Wang, Tao-Ming, Jun-Lin Kuo +1
Computer Science · Mathematics · #05C62 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Constraint Satisfaction and Optimization #FOS: Mathematics #math.CO #msc:05C62 #msc:05C69
paper · pdf · doi:10.48550/arxiv.0804.2584
15 pages, 3 figures
arxiv created 2008/04/16 · openalex publication_date 2008/04/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1994 S. McGuinness showed that any greedy clique decompo- sition of an n-vertex graph has at most \lfloor n2/4 \rfloor cliques (The greedy clique decomposition of a graph, J. Graph Theory 18 (1994) 427-430), where a clique decomposition means a clique partition of the edge set and a greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. This result solved a conjecture by P. Winkler. A multifamily set rep- resentation of a simple graph G is a family of sets, not necessarily distinct, each member of which represents a vertex in G, and the in- tersection of two sets is non-empty if and only if two corresponding vertices in G are adjacent. It is well known that for a graph G, there is a one-to-one correspondence between multifamily set representations and clique coverings of the edge set. Further for a graph one may have a one-to-one correspondence between particular multifamily set rep- resentations with intersection size at most one and clique partitions of the edge set. In this paper, we study for an n-vertex graph the variant of the set representations using a family of distinct sets, including the greedy way to get the corresponding clique partition of the edge set of the graph. Similarly, in this case, we obtain a result that any greedy clique decomposition of an n-vertex graph has at most \lfloor n2/4 \rfloor cliques.