Extremal homomorphism bound for graphs with fixed minimum degree

About 13 years old · traced to

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 n≥c(δ,H)n\geq c(\delta,H) and G∈G(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.

References

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.