Mangoes and Blueberries

• Published in 1999
In the collections
We prove the following conjecture of Erdős and Hajnal: For every integer $k$ there is an $f(k)$ such that if for a graph $G$, every subgraph $H$ of $G$ has a stable set containing vertices, then $G$ contains a set $X$ of at most $f(k)$ vertices such that $G−X$ is bipartite. This conjecture was related to me by Paul Erdős at a conference held in Annecy during July of 1996. I regret not being able to share the answer with him.

Other information

key
MangoesandBlueberries
type
article
2020-09-21
date_published
1999-11-14
publisher
Bolyai Society – Springer-Verlag
fulltext_html_url
journal
Combinatorica
issn
1439-6912
volume
19
issue
2
identifier
doi:10.1007/s004930050056
doi
10.1007/s004930050056
pages
267-296

BibTeX entry

@article{MangoesandBlueberries,
key = {MangoesandBlueberries},
type = {article},
title = {Mangoes and Blueberries},
author = {Bruce Reed},
abstract = {We prove the following conjecture of Erd{\H{o}}s and Hajnal:

For every integer $k$ there is an $f(k)$ such that if for a graph $G$, every subgraph $H$ of $G$ has a stable set containing vertices, then $G$ contains a set $X$ of at most $f(k)$ vertices such that $G−X$ is bipartite.

This conjecture was related to me by Paul Erd{\H{o}}s at a conference held in Annecy during July of 1996. I regret not being able to share the answer with him.},
comment = {},
date_published = {1999-11-14},
collections = {attention-grabbing-titles,food},
}