On Greedy Clique Decompositions and Set Representations of Graphs

Simple item page
dc.creatorWang, Tao-Ming
dc.creatorKuo, Jun-Lin
dc.date2008-04-16
dc.date.accessioned2026-07-07T09:32:56Z
dc.date.available2026-07-07T09:32:56Z
dc.descriptionIn 1994 S. McGuinness showed that any greedy clique decompo- sition of an n-vertex graph has at most $\lfloor n^2/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 n^2/4 \rfloor$ cliques.
dc.description15 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/0804.2584
dc.identifierhttp://arxiv.org/abs/0804.2584
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/158961
dc.subjectCombinatorics
dc.subject05C62; 05C69
dc.titleOn Greedy Clique Decompositions and Set Representations of Graphs
dc.typetext

Files

Collections

arXiv