✦ LIBER ✦

Independence number and clique minors

✍ Scribed by Ken-ichi Kawarabayashi; Zi-Xia Song

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 122 KB
Volume: 56
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20268

No coin nor oath required. For personal study only.

✦ Synopsis

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 independence number and the number of vertices of G, respectively. Motivated by this fact, it is shown that $(2\alpha({G})-{2})\cdot {h}({G})\geq |{G}|$ for every graph G with $\alpha({G})\geq {3}$. This improves a theorem of Duchet and Meyniel and a recent improvement due to Kawarabayashi et al. © Wiley Periodicals, Inc. J. Graph Theory 56: 219–226, 2007

📜 SIMILAR VOLUMES

Clique Minors in Graphs and Their Comple

Clique Minors in Graphs and Their Complements

✍ Bruce Reed; Robin Thomas 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 107 KB

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t 1 be an integer, and let G be a graph on n vertices with no minor isomorphic to K t+1 . Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has

Surfaces, Tree-Width, Clique-Minors, and

Surfaces, Tree-Width, Clique-Minors, and Partitions

✍ Guoli Ding; Bogdan Oporowski; Daniel P. Sanders; Dirk Vertigan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 214 KB

In 1971, Chartrand, Geller, and Hedetniemi conjectured that the edge set of a planar graph may be partitioned into two subsets, each of which induces an outerplanar graph. Some partial results towards this conjecture are presented. One such result, in which a planar graph may be thus edge partitione

Local and Global Clique Numbers

✍ N. Linial; Y. Rabinovich 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 416 KB

Consider a graph $G$ with the property that any set of $p$ vertices in $G$ contains a $q$-clique. Fairly tight lower bounds are proved on the clique number of $G$ as a function of $p, q$ and the number of vertices in $G$. 1994 Academic Press, Inc.

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

Another note on cliques and independent

Another note on cliques and independent sets

✍ Fred Galvin 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB 👁 2 views

A note on cliques and independent sets

✍ Entringer, Roger C.; Goddard, Wayne; Henning, Michael A. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 2 views

For integers m, n ≥ 2, let f (m, n) be the minimum order of a graph where every vertex belongs to both a clique of cardinality m and an independent set of cardinality n. We show that f (m, n) = ( √ m -1 + √ n -1) 2 .