Existence of extremal graphs for clique density

From papers

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 t3t\geq 3 and 3ωΔ+13\leq\omega\leq\Delta+1, there exists a graph GG(Δ,ω)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.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.