Extremal homomorphism bound for graphs with fixed minimum degree

Fix an integer δ1\delta\geq 1 and a graph HH. Let G(n,δ)\mathcal{G}(n,\delta) be the family of all nn-vertex graphs with minimum degree δ\delta, and let c(δ,H)c(\delta,H) be a constant depending on δ\delta and HH. Minimum-degree homomorphism conjecture. For nc(δ,H)n\geq c(\delta,H) and GG(n,δ)G\in\mathcal{G}(n,\delta),

hom(G,H)max{hom(Kδ+1,H)nδ+1,hom(Kδ,δ,H)n2δ,hom(Kδ,nδ,H)}.\hom(G,H) \leq \max\{\hom(K_{\delta+1},H)^{\frac{n}{\delta+1}}, \hom(K_{\delta,\delta},H)^{\frac{n}{2\delta}}, \hom(K_{\delta,n-\delta},H)\}.

This conjecture proposes three possible asymptotic extremal constructions: disjoint unions of (δ+1)(\delta+1)-cliques, disjoint unions of copies of Kδ,δK_{\delta,\delta}, and the complete bipartite graph Kδ,nδK_{\delta,n-\delta}. It is motivated by exact results for independent-set colorings and remains open in the stated generality.

Sources & referencesView supporting material

Primary source

John Engbers, “Extremal H-colorings of graphs with fixed minimum degree”, arXiv:1307.5919 (2016).

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.