## Abstract

A perfect Kr-tiling in a graph G is a collection of vertex-disjoint copies of the clique Kr in G covering every vertex of G. The famous Hajnal-Szemerédi theorem determines the minimum degree threshold for forcing a perfect Kr-tiling in a graph G. The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph G labels from {-1, 1}, and one seeks substructures F of G that have 'high' discrepancy (i.e. the sum of the labels of the edges in F is far from 0). In this paper we determine the minimum degree threshold for a graph to contain a perfect Kr-tiling of high discrepancy.

Original language | English (US) |
---|---|

Pages (from-to) | 444-459 |

Number of pages | 16 |

Journal | Combinatorics Probability and Computing |

Volume | 30 |

Issue number | 3 |

DOIs | |

State | Published - May 30 2021 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics