Minimum Degree Threshold for $H$-factors with High Discrepancy
Given a graph $H$, a perfect $H$-factor in a graph $G$ is a collection of vertex-disjoint copies of $H$ spanning $G$. Kühn 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/\chi_{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'$ of $G$, we say that $G'$ has high discrepancy if it contains significantly (linear in $n$) more edges of one color than the other. Balogh, Csaba, Pluhár 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$.
Authors
- Micha Christoph
- Domagoj Bradač (ORCID: https://orcid.org/0000-0002-8058-7782)
- Lior Gishboliner (ORCID: https://orcid.org/0000-0003-0688-8111)
Institutions
- ETH Zurich (CH)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2024-09-20
- DOI
- https://doi.org/10.37236/12145
- Citations
- 4
- Primary Topic
- Mathematical Approximation and Integration
- Type
- article
- Field-Weighted Citation Impact
- 2.93