The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor (Q2662350): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 2003.12960 / rank | |||
Normal rank |
Revision as of 08:52, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor |
scientific article |
Statements
The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor (English)
0 references
12 April 2021
0 references
Summary: We prove that for every integer \(k\), there exists \(\varepsilon>0\) such that for every \(n\)-vertex graph with no pivot-minors isomorphic to \(C_k\), there exist disjoint sets \(A, B\subseteq V(G)\) such that \(|A|,|B|\geqslant\varepsilon n\), and \(A\) is complete or anticomplete to \(B\). This proves the analog of the Erdős-Hajnal conjecture for the class of graphs with no pivot-minors isomorphic to \(C_k\).
0 references
Erdős-Hajnal conjecture
0 references
vertex-minors
0 references