✦ LIBER ✦

On clique covers and independence numbers of graphs

✍ Scribed by Robert C. Brigham; Ronald D. Dutton

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 485 KB
Volume: 44
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(83)90054-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On antichain intersection numbers, total

On antichain intersection numbers, total clique covers and regular graphs

✍ Morimasa Tsuchiya 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 742 KB

In this paper, we consider total clique covers and intersection numbers on multifamilies. We determine the antichain intersection numbers of graphs in terms of total clique covers. From this result and some properties of intersection graphs on multifamilies, we determine the antichain intersection n

Clique numbers of graphs

✍ Paul Erdös; Marcel Erné 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 337 KB

For each natural number n, denote by G(n) the set of all numbers c such that there exists a graph with exactly c cliques (i.e., complete subgraphs) and n vertices. We prove the asymptotic estimate Ia(n)l = 0(2"n -z/5) and show that all natural numbers between n + 1 and 2 "-6"5~6 belong to G(n). Thus

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

Upper bounds on the edge clique cover nu

Upper bounds on the edge clique cover number of a graph

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

Independent Arithmetic Progressions in C

Independent Arithmetic Progressions in Clique-Free Graphs on the Natural Numbers

✍ David S. Gunderson; Imre Leader; Hans Jürgen Prömel; Vojtěch Rödl 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 179 KB

We show that if G is a K r -free graph on N, there is an independent set in G which contains an arbitrarily long arithmetic progression together with its difference. This is a common generalization of theorems of Schur, van der Waerden, and Ramsey. We also discuss various related questions regarding

Independence number and clique minors

✍ Ken-ichi Kawarabayashi; Zi-Xia Song 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract The Hadwiger number ${h}({G})$ of a graph __G__ is the maximum integer __t__ such that ${K}\_{t}$ is a minor of __G__. Since $\chi({G})\cdot\alpha({G})\geq |{G}|$, Hadwiger's conjecture implies that ${h}({G})\cdot \alpha({G})\geq |{G}|$, where $\alpha({G})$ and $|{G}|$ denote the indepe