✦ LIBER ✦

On the partition and coloring of a graph by cliques

✍ Scribed by W.D. Wallis; Guo-Hui Zhang

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 859 KB
Volume: 120
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90576-f

No coin nor oath required. For personal study only.

✦ Synopsis

Wallis, W.D. and G.-H. Zhang, On the partition and coloring of a graph by cliques, Discrete Mathematics 120 (1993) 191-203.

We first introduce the concept of the k-chromatic index of a graph, and then discuss some of its properties. A characterization of the clique partition number of the graph G V K', for any simple graph G is given, together with some of its applications.

Graphs with maximum valency 3 are also considered.

📜 SIMILAR VOLUMES

Partition graphs and coloring numbers of

Partition graphs and coloring numbers of a graph

✍ E. Sampathkumar; V.N. Bhave 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 288 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

Partitions of graphs into one or two ind

Partitions of graphs into one or two independent sets and cliques

✍ Andreas Brandstädt 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 417 KB

It is shown in this note that it can be recognized in polynomial time whether the vertex set of a finite undirected graph can be partitioned into one or two independent sets and one or two cliques. Such graphs generalize bipartite and split graphs and the result also shows that it can be recognized

On the radius and diameter of the clique

On the radius and diameter of the clique graph

✍ Ronald D. Dutton; Robert C. Brigham 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 124 KB

An upper bound on the number of cliques

An upper bound on the number of cliques in a graph

✍ Martin Farber; Mihály Hujter; Zsolt Tuza 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

Coloring the square of a planar graph

✍ Jan van den Heuvel; Sean McGuinness 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract We prove that for any planar graph __G__ with maximum degree Δ, it holds that the chromatic number of the square of __G__ satisfies χ(__G__^2^) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002