Structural properties of bipartite subgraphs

arXiv2106.12099MaRDI QIDQ6371013FDOQ6371013

David R. Wood, Robert Hickingbotham

Publication date: 22 June 2021

Abstract: This paper establishes sufficient conditions that force a graph to contain a bipartite subgraph with a given structural property. In particular, let $$ be any of the following graph parameters: Hadwiger number, Haj'{o}s number, treewidth, pathwidth, and treedepth. In each case, we show that there exists a function $f$ such that every graph $G$ with $$ contains a bipartite subgraph $hatGsubseteqG$ with $$.

This page was built for publication: Structural properties of bipartite subgraphs

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