Towards Erdős-Hajnal for graphs with no 5-hole

DOI10.1007/S00493-019-3957-8MaRDI QIDQ2288355zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Jacob Fox, Sophie Spirkl, Alex Scott, Paul Seymour

Publication date 17 January 2020

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.03588

zbMATH Keywords

cliquesextremal problemsstable set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The Erdos-Hajnal conjecture says that for every graph $H$ there exists $c>0$ such that $max(alpha(G),omega(G))ge{n}^c$ for every $H$-free graph $G$ with $n$ vertices, and this is still open when $H=C_5$. Until now the best bound known on $max(alpha(G),omega(G))$ for $C_5$-free graphs was the general bound of Erdos and Hajnal, that for all $H$, $max(alpha(G),omega(G))ge{2}^{Omega(sqrtlogn)}$ if $G$ is $H$-free. We improve this when $H=C_5$ to $max(alpha(G),omega(G))ge{2}^{Omega(sqrtlognloglogn)}.$

Review text

In this paper, all graphs are finite and have no loops or parallel edges. The cardinalities of the largest stable sets and cliques in a graph \(G = (V, E)\) with \(|V|=n\) are denoted by \(\alpha(G)\) and \(\omega(G)\), respectively. For two graphs \(G\) and \(H\) we say that \(G\) contains \(H\) if some induced subgraph of \(G\) is isomorphic to \(H\) and \(G\) is \(H\)-free otherwise. The Erdős-Hajnal conjecture says that for every graph \(H\) there exists \(c > 0\) such that \(\max(\alpha(G), \omega(G)) \geq n^c\) for every \(H\)-free graph \(G\) and this is still open when \(H=C_5\) (\(C_5\) denotes the cycle of length 5). The best general bound for the Erdős-Hajnal conjecture to date \(\max((\alpha(G), \omega(G)) \geq n^{c \sqrt{log(n)}}\) was proved by \textit{P. Erdős} and \textit{A. Hajnal} [Discrete Appl. Math. 25, No. 1--2, 37--52 (1989; Zbl 0715.05052)] for every \(H\)-free graph \(G\) (logarithm is of base 2). This was also the known bound for \(H = C_5\). In this paper, the authors improve the bound to \(\max((\alpha(G), \omega(G)) \geq n^{c \sqrt{log(n) log(n) log(n)}}\) for every \(C_5\)-free graph \(G\).

Recommendations

• The Erdős-Hajnal conjecture. A survey
• The Erdős-Hajnal conjecture for long holes and antiholes
• Erdős–Hajnal for graphs with no 5‐hole
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• Excluding paths and antipaths
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
• Erdős-Hajnal for cap-free graphs
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• A note on hitting maximum and maximal cliques with a stable set
• Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs

Cited in

(15)

• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• Erdős-Hajnal-type results for monotone paths
• Erdős-Hajnal for cap-free graphs
• A superlinear lower bound on the number of 5-holes
• Erdős-Lovász Tihany conjecture for graphs with forbidden holes
• The Erdős-Hajnal conjecture for long holes and antiholes
• Induced C₅-free graphs of fixed density: counting and homogeneous sets
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Polynomial bounds for chromatic number II: Excluding a star‐forest
• Erdős–Hajnal for graphs with no 5‐hole
• Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
• Towards the Erdős-Hajnal conjecture for P₅-free graphs
• Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph
• Hitting all maximum stable sets in P₅-free graphs
• Pure Pairs. IX. Transversal Trees

This page was built for publication: Towards Erdős-Hajnal for graphs with no 5-hole

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2288355)