Pure pairs. II: Excluding all subdivisions of a graph

DOI10.1007/S00493-020-4024-1MaRDI QIDQ2043764zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Alex Scotty, Sophie Spirkl, Paul Seymour

Publication date 3 August 2021

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

pure pairssubdivisions of a graphErdős-Hajnal conjecture

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: We prove for every graph H there exists a>0 such that, for every graph G with at least two vertices, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least a|G| neighbours, or there are two disjoint sets A,B of at least a|G| vertices such that no edge joins A and B. It follows that for every graph H, there exists c>0 such that for every graph G, if no induced subgraph of G or its complement is a subdivision of H, then G has a clique or stable set of cardinality at least |G|^c. This is related to the Erdos-Hajnal conjecture.

Recommendations

• Pure pairs. I: Trees and linear anticomplete pairs
• Almost all \(H\)-free graphs have the Erdős-Hajnal property
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs
• Caterpillars in Erdős-Hajnal
• The Erdős-Hajnal conjecture. A survey

Cites work

• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 3628985 (Why is no real title available?)
• A bipartite analogue of Dilworth's theorem
• Caterpillars in Erdős-Hajnal
• Crossing patterns of semi-algebraic sets
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Excluding hooks and their complements
• Excluding paths and antipaths
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• On universality of graphs with uniformly distributed edges
• Pure pairs. I: Trees and linear anticomplete pairs
• Ramsey-type theorems
• Some remarks on the theory of 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
• Triangle-free intersection graphs of line segments with large chromatic number

Cited in

(12)

• Pure pairs. I: Trees and linear anticomplete pairs
• Towards the Erdős-Hajnal conjecture for \(P_5\)-free graphs
• Strong Erdős-Hajnal properties in chordal graphs
• Pure pairs. V: Excluding some long subdivision
• Erdős-Hajnal-type results for monotone paths
• Erdős–Hajnal for graphs with no 5‐hole
• Pure Pairs. IX. Transversal Trees
• String graphs have the Erdős-Hajnal property
• Graphs of large chromatic number
• Pure pairs. IV: Trees in bipartite graphs
• Packing and covering induced subdivisions
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs

This page was built for publication: Pure pairs. II: Excluding all subdivisions of a graph

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