Minimum Degree Threshold for H-factors with High Discrepancy

MaRDI QIDQ6427776zbMATH OpenFDO

Authors Domagoj Bradač, Micha Christoph, Lior Gishboliner

Publication date 27 February 2023

Abstract: Given a graph $H$, a perfect $H$-factor in a graph $G$ is a collection of vertex-disjoint copies of $H$ spanning $G$. K"uhn and Osthus showed that the minimum degree threshold for a graph $G$ to contain a perfect $H$-factor is either given by $1-1/chi(H)$ or by $1-1/ch{i}_{cr}(H)$ depending on certain natural divisibility considerations. Given a graph $G$ of order $n$, a $2$-edge-coloring of $G$ and a subgraph $G^{\prime }$ of $G$, we say that $G^{\prime }$ has high discrepancy if it contains significantly (linear in $n$) more edges of one color than the other. Balogh, Csaba, Pluh'ar and Treglown asked for the minimum degree threshold guaranteeing that every 2-edge-coloring of $G$ has an $H$-factor with high discrepancy and they settled the case where $H$ is a clique. Here we completely resolve this question by determining the minimum degree threshold for high discrepancy of $H$-factors for every graph $H$.

This page was built for publication: Minimum Degree Threshold for $H$-factors with High Discrepancy

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