On Greedy Clique Decompositions and Set Representations of Graphs
From MaRDI portal
Publication:6209158
arXiv0804.2584MaRDI QIDQ6209158FDOQ6209158
Authors: Tao-Ming Wang, Jun-Lin Kuo 
Publication date: 16 April 2008
Abstract: In 1994 S. McGuinness showed that any greedy clique decompo- sition of an n-vertex graph has at most 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 cliques.
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
This page was built for publication: On Greedy Clique Decompositions and Set Representations of Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6209158)
