Journal article
Pure pairs. V. Excluding some long subdivision
- Abstract:
-
A pure pair in a graph $G$ is a pair $A,B$ of disjoint subsets of $V(G)$ such that $A$ is complete or anticomplete to $B$. Jacob Fox showed that for all $\epsilon>0$, there is a comparability graph $G$ with $n$ vertices, where $n$ is large, in which there is no pure pair $A,B$ with $|A|,|B|\ge \epsilon n$. He also proved that for all $c>0$ there exists $\epsilon>0$ such that for every comparability graph $G$ with $n>1$ vertices, there is a pure pair $A,B$ with $|A|,|B|\ge \epsilon...
Expand abstract
- Publication status:
- Accepted
- Peer review status:
- Peer reviewed
Actions
Authors
Bibliographic Details
- Publisher:
- Springer Nature Publisher's website
- Journal:
- Combinatorica Journal website
- Acceptance date:
- 2023-01-24
- EISSN:
-
1439-6912
- ISSN:
-
0209-9683
Item Description
Terms of use
- Copyright date:
- 2021
- Notes:
- This article has been accepted for publication in Combinatorica.
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record