The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor (Q2662350)
From MaRDI portal
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
0 references