Mangoes and Blueberries

• Published in 1999
• Added on 2020-09-21

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.

Links

• https://link.springer.com/article/10.1007/s004930050056
• https://link.springer.com/content/pdf/10.1007/s004930050056.pdf

Other information

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_added = {2020-09-21},
	date_published = {1999-12-07},
	urls = {https://link.springer.com/article/10.1007/s004930050056,https://link.springer.com/content/pdf/10.1007/s004930050056.pdf},
	collections = {attention-grabbing-titles,food},
	url = {https://link.springer.com/article/10.1007/s004930050056 https://link.springer.com/content/pdf/10.1007/s004930050056.pdf},
	year = 1999,
	urldate = {2020-09-21},
	publisher = {Bolyai Society – Springer-Verlag},
	fulltext_html_url = {https://link.springer.com/article/10.1007/s004930050056},
	journal = {Combinatorica},
	issn = {1439-6912},
	volume = 19,
	issue = 2,
	identifier = {doi:10.1007/s004930050056},
	doi = {10.1007/s004930050056},
	pages = {267-296}
}