Back to Search
Start Over
The Erd\H{o}s-Hajnal property for graphs with no fixed cycle as a pivot-minor
- Source :
- Electron. J. Combin., 28(April 2021), #P2.9
- Publication Year :
- 2020
-
Abstract
- We prove that for every integer $k$, there exists $\varepsilon > 0$ such that for every n-vertex graph $G$ with no pivot-minor isomorphic to $C_k$, there exist disjoint sets $A,B \subseteq V(G)$ such that $|A|,|B| \geq \varepsilon n$, and $A$ is either complete or anticomplete to $B$. This proves the analog of the Erd\H{o}s-Hajnal conjecture for the class of graphs with no pivot-minor isomorphic to $C_k$.<br />Comment: 13 pages, 4 figures
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- Electron. J. Combin., 28(April 2021), #P2.9
- Publication Type :
- Report
- Accession number :
- edsarx.2003.12960
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.37236/9536