Excluding hooks and their complements

zbMath1395.05085arXiv1508.00634MaRDI QIDQ1671647

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

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

Mathematics Subject Classification ID

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

Related Items (5)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Clique versus independent set
• Tournaments with near-linear transitive subsets
• Excluding paths and antipaths
• Ramsey-type theorems
• A bipartite analogue of Dilworth's theorem
• The Erdős-Hajnal conjecture for bull-free graphs
• Density theorems for bipartite graphs and related Ramsey-type results
• On universality of graphs with uniformly distributed edges
• Recognizing claw-free perfect graphs
• Expressing combinatorial optimization problems by linear programs
• A description of claw-free perfect graphs
• An introduction to clique minimal separator decomposition
• Forcing large transitive subtournaments
• The Erdős-Hajnal conjecture for paths and antipaths
• EH-suprema of tournaments with no nontrivial homogeneous sets
• Crossing patterns of semi-algebraic sets
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• The Erdös--Hajnal Conjecture for Long Holes and Antiholes
• Upper Bounds for Erdös-Hajnal Coefficients of Tournaments
• The Erdös-Hajnal Conjecture-A Survey
• Line Graphs of Helly Hypergraphs
• Independence and Efficient Domination on P ₆ -free Graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Some remarks on the theory of graphs
• Induced Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs

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