PreprintarXiv licencearXiv
The Remaining K4-Free Case in the Multipartite Clique Problem
Abstract
For integers n,r,t with 2≤ t≤ r−1, let f(n,r,t+1) denote the largest possible minimum degree of a balanced r-partite graph with parts of size n and containing no copy of Kt+1. Lo, Treglown and Zhao identified f(n,7,4) as the only remaining case in their treatment of the K4-free family. I determine this function for every n≥1. First, the corresponding three-colourable extremum δ(n,7,3) is reduced to a 7×3 integer matrix problem and determined exactly. Second, a structural argument shows that every balanced $7$-partite K4-free graph G with δ(G)>132/31n is three-colourable. Consequently, f(n,7,4)=⌊30n/7⌋ except when n≡4pmod7 and n≥11, where it is one less.
Related
- The 𝒜α-Spectral Turán Problem for s-Clique Tensors of Kr+1-Free Graphs
- Chromatic Extremal Thresholds and the Multipartite K4-Free Problem
- Elimination of René Peschmann's 968 Remaining Hard Fibers for the Perfect Cuboid Problem
- Counterexamples to two conjectures on the diameter of clique-free graphs
- On the Large Λ Asymptotics of the One Phase Bernoulli Free Boundary Problem
BibTeX
@misc{kasugai2026remaining,
title = {{The Remaining $K_4$-Free Case in the Multipartite Clique Problem}},
author = {Yuuki Kasugai},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19177},
eprint = {2609.19177},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19177},
}
RIS
TY - UNPB
TI - The Remaining K_4-Free Case in the Multipartite Clique Problem
AU - Yuuki Kasugai
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.19177
UR - https://arxiv.org/abs/2609.19177
AB - For integers n,r,t with 2≤ t≤ r−1, let f(n,r,t+1) denote the largest possible minimum degree of a balanced r-partite graph with parts of size n and containing no copy of K_t+1. Lo, Treglown and Zhao identified f(n,7,4) as the only remaining case in their treatment of the K_4-free family. I determine this function for every n≥1. First, the corresponding three-colourable extremum δ(n,7,3) is reduced to a 7×3 integer matrix problem and determined exactly. Second, a structural argument shows that every balanced $7$-partite K_4-free graph G with δ(G)>132/31n is three-colourable. Consequently, f(n,7,4)=⌊30n/7⌋ except when n≡4pmod7 and n≥11, where it is one less.
ER -