Excluding pairs of graphs

DOI10.1016/J.JCTB.2014.01.001MaRDI QIDQ402589zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Alex Scott, Paul Seymour

Publication date 28 August 2014

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphsRamsey theoremcograph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Generalized Ramsey theory (05C55)

Abstract: For a graph $G$ and a set of graphs $mathcalH$, we say that $G$ is {em $mathcalH$-free} if no induced subgraph of $G$ is isomorphic to a member of $mathcalH$. Given an integer $P>0$, a graph $G$, and a set of graphs $mathcalF$, we say that $G$ {em admits an $(mathcalF,P)$-partition} if the vertex set of $G$ can be partitioned into $P$ subsets $X_1,\mathrm{...},X_P$, so that for every $iin1,\mathrm{...},P$, either $|X_i|=1$, or the subgraph of $G$ induced by $X_i$ is $F$-free for some $FinmathcalF$. Our first result is the following. For every pair $(H,J)$ of graphs such that $H$ is the disjoint union of two graphs $H_1$ and $H_2$, and the complement $J^c$ of $J$ is the disjoint union of two graphs $J_1^c$ and $J_2^c$, there exists an integer $P>0$ such that every $H,J$-free graph has an $(H_1,H_2,J_1,J_2,P)$-partition. Using a similar idea we also give a short proof of one of the results of cite{heroes}. Our final result is a construction showing that if $H,J$ are graphs each with at least one edge, then for every pair of integers $r,k$ there exists a graph $G$ such that every $r$-vertex induced subgraph of $G$ is $H,J$-split, but $G$ does not admits an $(H,J,k)$-partition.

Recommendations

• Splits with forbidden subgraphs
• Partitioning cographs into two forests and one independent set
• Vertex partitions of graphs into cographs and stars
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs
• Partitions of graphs into cographs

Cites work

• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Extending the Gyárfás-Sumner conjecture
• On a property of the class of n-colorable graphs
• Tournaments and colouring

Cited in

(7)

• Unavoidable tournaments
• Extending the Gyárfás-Sumner conjecture
• scientific article; zbMATH DE number 475621 (Why is no real title available?)
• Splits with forbidden subgraphs
• Detours in directed graphs
• Polynomial bounds for chromatic number. VIII: Excluding a path and a complete multipartite graph
• Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model

This page was built for publication: Excluding pairs of graphs

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