✦ LIBER ✦

Clique coverings and partitions of line graphs

✍ Scribed by Bo-Jr Li; Gerard J. Chang

Book ID: 108113827
Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 153 KB
Volume: 308
Category: Article
ISSN: 0012-365X
DOI: 10.1016/j.disc.2007.04.059

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Clique covering and clique partition in

Clique covering and clique partition in generalizations of line graphs

✍ Erich Prisner 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 387 KB

On the number of distinct minimal clique

On the number of distinct minimal clique partitions and clique covers of a line graph

✍ Sean McGuinness; Rolf Rees 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 812 KB

Let G be a line graph. Orlin determined the clique covering and clique partition numbers cc(G) and cp(G). We obtain a constructive proof of Orlin's result and in doing so we are able to completely enumerate the number of distinct minimal clique covers and partitions of G, in terms of easily calculab

Clique partitions and clique coverings

✍ Paul Erd'́os; Ralph Faudree; Edward T. Ordman 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 575 KB

Several new tools are presented for determining the number of cliques needed to (edge-)partition a graph. For a graph on n vertices, the clique partition number can grow et-? times as fast as the clique covering number, where c is at least l/64. If in a clique on n vertices, the edges between cn" ve

Clique and anticlique partitions of grap

Clique and anticlique partitions of graphs

✍ Krzysztof Bryś; Zbigniew Lonc 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 408 KB

In the paper we prove that, for a fixed k, the problem of deciding whether a graph admits a partition of its vertex set into k-element cliques or anticliques (i.e. independent sets) is polynomial.

Extremal clique coverings of complementa

Extremal clique coverings of complementary graphs

✍ D. de Caen; P. Erdős; N. J. Pullmann; N. C. Wormald 📂 Article 📅 1986 🏛 Springer-Verlag 🌐 English ⚖ 264 KB

On clique partitions of split graphs

✍ W.D. Wallis; J. Wu 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 204 KB

Wallis, W.D. and J. Wu, On clique partitions of split graphs, Discrete Mathematics 92 (1991) 427-429. Split graphs are graphs formed by taking a complete graph and an empty graph disjoint from it and some or all of the possible edges joining the two. We prove that the problem of deciding the clique