𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the connection between chromatic number, maximal clique and minimal degree of a graph

✍ Scribed by B. Andrásfai; P. Erdös; V.T. Sós

Publisher
Elsevier Science
Year
1974
Tongue
English
Weight
606 KB
Volume
8
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

A remark on the number of vertices of de
A remark on the number of vertices of degree k in a minimally k-edge-connected graph
✍ Mao-cheng Cai 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 395 KB

Let G be a minimally k-edge-connected simple graph and u\*(G) be the number of vertices of degree k in G. proved that (i) uk(G) 2 l(jGl -1)/(2k + l)] + k + 1 for even k, and (ii) uI(G) 2 [lGl/(k + l)] + k for odd k 35 and u,(G) 2 lZlGl/(k + l)] + k -2 for odd k 27, where ICI denotes the number of v

A note on the line-distinguishing chroma
A note on the line-distinguishing chromatic number and the chromatic index of a graph
✍ N. Zagaglia Salvi 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let λ(__G__) be the line‐distinguishing chromatic number and __x__′(__G__) the chromatic index of a graph __G__. We prove the relation λ(__G__) ≥ __x__′(__G__), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.