✦ LIBER ✦

On planar intersection graphs with forbidden subgraphs

✍ Scribed by János Pach; Micha Sharir

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 154 KB
Volume: 59
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20332

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let ${\cal C}$ be a family of n compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with k vertices in each of its classes. Then $G({\cal C})$ has at most n times a polylogarithmic number of edges, where the exponent of the logarithmic factor depends on k. In the case where ${\cal C}$ consists of convex sets, we improve this bound to O(n log n). If in addition k = 2, the bound can be further improved to O(n). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 205–214, 2008

📜 SIMILAR VOLUMES

Connected subgraphs with small degree su

Connected subgraphs with small degree sums in 3-connected planar graphs

✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

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

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 \_(