Excluding hooks and their complements

MaRDI QIDQ1671647zbMATH OpenFDO

Authors Krzysztof Choromanski, Dvir Falik, Anita Liebenau, Viresh Patel, Marcin Pilipczuk

Publication date 7 September 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.00634, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p27

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Extremal combinatorics (05D99)

Abstract: The celebrated Erdos-Hajnal conjecture states that for every $n$-vertex undirected graph $H$ there exists $eps(H)>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or an independent set of size at least $n^{eps(H)}$. A weaker version of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both $H$ and its complement $H^{compl}$. We show that the weaker conjecture holds if $H$ is any path with a pendant edge at its third vertex; thus we give a new infinite family of graphs for which the conjecture holds.

Review text

Summary: The long-standing Erdős-Hajnal conjecture states that for every \(n\)-vertex undirected graph \(H\) there exists \(\varepsilon(H)>0\) such that every graph \(G\) that does not contain \(H\) as an induced subgraph contains a clique or an independent set of size at least \(n^{\varepsilon(H)}\). A natural weakening of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both \(H\) and its complement \(H^{\text{c}}\). These conjectures have been shown to hold for only a handful of graphs: it is not even known if they hold for all graphs on \(5\) vertices. In a recent breakthrough, the symmetrized version of the Erdős-Hajnal conjecture was shown to hold for all paths. The goal of this paper is to show that the symmetrized conjecture holds for all trees on 6 (or fewer) vertices. In fact this is a consequence of showing that the symmetrized conjecture holds for any path with a pendant edge at its third vertex; thus we also give a new infinite family of graphs for which the symmetrized conjecture holds.

Recommendations

• Excluding paths and antipaths
• The Erdős-Hajnal conjecture for paths and antipaths
• Pure pairs. I: Trees and linear anticomplete pairs
• The Erdős-Hajnal conjecture for long holes and antiholes
• Erdős–Hajnal for graphs with no 5‐hole

Cites work

• A bipartite analogue of Dilworth's theorem
• A description of claw-free perfect graphs
• An introduction to clique minimal separator decomposition
• Clique versus independent set
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Crossing patterns of semi-algebraic sets
• Density theorems for bipartite graphs and related Ramsey-type results
• EH-suprema of tournaments with no nontrivial homogeneous sets
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Excluding paths and antipaths
• Expressing combinatorial optimization problems by linear programs
• Forcing large transitive subtournaments
• scientific article; zbMATH DE number 3628985 (Why is no real title available?)
• scientific article; zbMATH DE number 1552836 (Why is no real title available?)
• Independence and Efficient Domination on P ₆ -free Graphs
• Independent set in P₅-free graphs in polynomial time
• Induced Ramsey-type theorems
• Line Graphs of Helly Hypergraphs
• On universality of graphs with uniformly distributed edges
• Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs
• Recognizing claw-free perfect graphs
• Some remarks on the theory of graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• The Erdős-Hajnal conjecture for long holes and antiholes
• The Erdős-Hajnal conjecture for paths and antipaths
• The Erdős-Hajnal conjecture. A survey
• Tournaments with near-linear transitive subsets
• Treewidth and minimum fill-in: Grouping the minimal separators
• Upper bounds for Erdös-Hajnal coefficients of tournaments

Cited in

(6)

• Pure pairs. II: Excluding all subdivisions of a graph
• Pure pairs. I: Trees and linear anticomplete pairs
• Caterpillars in Erdős-Hajnal
• Excluding paths and antipaths
• Erdős–Hajnal for graphs with no 5‐hole
• Graphs of large chromatic number

This page was built for publication: Excluding hooks and their complements

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