Excluding pairs of graphs

DOI10.1016/J.JCTB.2014.01.001zbMATH Open1297.05156arXiv1302.0812OpenAlexW2098242693MaRDI QIDQ402589FDOQ402589

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On a property of the class of n-colorable graphs
• Tournaments and colouring
• Extending the Gyárfás-Sumner conjecture

Cited In (7)

• Unavoidable tournaments
• Extending the Gyárfás-Sumner conjecture
• Title not available (Why is that?)
• 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)