Interesting Esoterica

Mangoes and Blueberries

Article by Bruce Reed
  • Published in 1999
  • Added on
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.

Links

Other information

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

BibTeX entry

@article{MangoesandBlueberries,
	title = {Mangoes and Blueberries},
	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.},
	url = {https://link.springer.com/article/10.1007/s004930050056 https://link.springer.com/content/pdf/10.1007/s004930050056.pdf},
	year = 1999,
	author = {Bruce Reed},
	comment = {},
	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},
	collections = {attention-grabbing-titles,food}
}