✦ LIBER ✦

On graphs with subgraphs having large independence numbers

✍ Scribed by Noga Alon; Benny Sudakov

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 is one of the several related questions raised by Erdős and Hajnal. We show that ${q}{(n)}= \Theta({\log}^{2} {n}/{\log}, {\log} ,{n})$, investigate the more general problem obtained by changing the parameters s and t, and discuss the connection to a related Ramsey‐type problem. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 149–157, 2007

📜 SIMILAR VOLUMES

On the Density of Subgraphs in a Graph w

On the Density of Subgraphs in a Graph with Bounded Independence Number

✍ Pavel Valtr 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(

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.

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

Subgraphs with a large cochromatic numbe

Subgraphs with a large cochromatic number

✍ Alon, Noga; Krivelevich, Michael; Sundakov, Benny 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB

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 ). Th

Interval coloring of (3,4)-biregular bip

Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs

✍ A. V. Pyatkin 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## Abstract An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph __G__ = (__A__,__B__;__E__) is (α, β)‐b

On graphs whose line graphs have crossin

On graphs whose line graphs have crossing number one

✍ Stanislav Jendrol'; Marián Kles̆c̆ 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract Necessary and sufficient conditions are given for a nonplanar graph to have a line graph with crossing number one. This corrects some errors in Kulli et al. 4. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 181–188, 2001