Existence of extremal graphs for clique density

At least 8 years old · documented by

Let G(Δ,ω)\mathcal{G}(\Delta,\omega) be the class of graphs with maximum degree at most Δ\Delta and clique number at most ω\omega, and let ft(Δ,ω)f_t(\Delta,\omega) be the supremum of ρt(G)\rho_t(G) over this class. Existence conjecture. For all t≥3t\geq 3 and 3≤ω≤Δ+13\leq\omega\leq\Delta+1, there exists a graph G∈G(Δ,ω)G\in\mathcal{G}(\Delta,\omega) such that

ρt(G)=ft(Δ,ω).\rho_t(G)=f_t(\Delta,\omega).

The paper notes that its results do not establish attainment of the supremum for all relevant parameters; this conjecture asks for an extremal graph in every allowed case and remains open.

References

Primary source

R. Kirsch and A. J. Radcliffe, “Maximizing the density of K_t's in graphs of bounded degree and clique number”, arXiv:1712.07769 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.