Pure pairs. II: Excluding all subdivisions of a graph

DOI10.1007/S00493-020-4024-1zbMATH Open1488.05427arXiv1804.01060OpenAlexW3177930638MaRDI QIDQ2043764FDOQ2043764

Paul Seymour, Maria Chudnovsky, Sophie Spirkl, Alex Scotty

Publication date: 3 August 2021

Published in: Combinatorica (Search for Journal in Brave)

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.

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

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Hajnal+conjecture&go=Go Erd��s-Hajnal conjecture]pure pairssubdivisions of a graph

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Triangle-free intersection graphs of line segments with large chromatic number
• The Erdős-Hajnal conjecture for paths and antipaths
• Crossing patterns of semi-algebraic sets
• The Erdős-Hajnal conjecture. A survey
• Some remarks on the theory of graphs
• A bipartite analogue of Dilworth's theorem
• On universality of graphs with uniformly distributed edges
• Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
• Ramsey-type theorems
• Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
• Excluding paths and antipaths
• Excluding hooks and their complements
• The Erdős-Hajnal conjecture for long holes and antiholes
• Pure pairs. I: Trees and linear anticomplete pairs
• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• Caterpillars in Erdős-Hajnal

Cited In (8)

• Towards the Erdős-Hajnal conjecture for \(P_5\)-free graphs
• Pure pairs. I: Trees and linear anticomplete pairs
• Strong Erdős-Hajnal properties in chordal graphs
• Erdős–Hajnal for graphs with no 5‐hole
• Erdős-Hajnal-type results for monotone paths
• String graphs have the Erdős-Hajnal property
• Graphs of large chromatic number
• 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)