✦ LIBER ✦

Subgraphs with a large cochromatic number

✍ Scribed by Alon, Noga; Krivelevich, Michael; Sundakov, Benny

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 66 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199708)25:4<295::aid-jgt7>3.0.co;2-f

No coin nor oath required. For personal study only.

✦ Synopsis

The cochromatic number of a graph G = (V, E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the chromatic number of G is n, then G contains a subgraph with cochromatic number at least Ω( n ln n ). This is tight, up to the constant factor, and settles a problem of Erdős and Gimbel.

📜 SIMILAR VOLUMES

On graphs with subgraphs having large in

On graphs with subgraphs having large independence numbers

✍ Noga Alon; Benny Sudakov 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB

## Abstract Let __G__ be a graph on __n__ vertices in which every induced subgraph on ${s}={\log}^{3}\, {n}$ vertices has an independent set of size at least ${t}={\log}\, {n}$. What is the largest ${q}={q}{(n)}$ so that every such __G__ must contain an independent set of size at least __q__? This

Subgraphs of large connectivity and chro

Subgraphs of large connectivity and chromatic number in graphs of large chromatic number

✍ N. Alon; D. Kleitman; C. Thomassen; M. Saks; P. Seymour 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

For each pair k, rn of natural numbers there exists a natural number f(k, rn) such that every f ( k , m)-chromatic graph contains a k-connected subgraph of chromatic number at least rn.

Cochromatic Number and the Genus of a Gr

Cochromatic Number and the Genus of a Graph

✍ H. Joseph Straight 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

## Abstract The cochromatic number of a graph __G__, denoted by __z__(__G__), is the minimum number of subsets into which the vertex set of __G__ can be partitioned so that each sbuset induces an empty or a complete subgraph of __G__. In this paper we introduce the problem of determining for a surf

Complete subgraphs with large degree sum

Complete subgraphs with large degree sums

✍ Ralph J. Faudree 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB

## Abstract Let __t__(__n, k__) denote the Turán number—the maximum number of edges in a graph on __n__ vertices that does not contain a complete graph __K__~k+1~. It is shown that if __G__ is a graph on __n__ vertices with __n__ ≥ __k__^2^(__k__ – 1)/4 and __m__ < __t__(__n, k__) edges, then __G__

Graphs with unavoidable subgraphs with l

Graphs with unavoidable subgraphs with large degrees

✍ L. Caccetta; P. Erdös; K. Vijayan 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

Let %(n, rn) denote the class of simple graphs on n vertices and rn edges and let G E %(n, rn). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a suff

Graphs with large total domination numbe

Graphs with large total domination number

✍ Michael A. Henning 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views