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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Minimum Degree Threshold for $H$-factors with High Discrepancy

Micha Christoph, Domagoj Bradač, Lior Gishboliner
4 citations
The Electronic Journal of Combinatorics
Mathematical Approximation and Integration
2.93
article

Minimum Degree Threshold for $H$-factors with High Discrepancy

Micha Christoph, Domagoj Bradač, Lior Gishboliner
article en
4 citations

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ü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$.

The Electronic Journal of CombinatoricsVol. 31(3)
ETH Zurich (CH)
Openalex Percentile: Top 9%
Mathematical Approximation and Integration
2.93
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.