Mixed chromatic-clique decomposition bound

For 0mk0\leq m\leq k, define

χm(k;Kn)=max{j=1mχ(Gj)+j=m+1kω(Gj)(G1,,Gk) is a k-decomposition of Kn}.\chi_m(k;K_n)=\max\left\{\sum_{j=1}^{m}\chi(G_j)+\sum_{j=m+1}^{k}\omega(G_j)\mid (G_1,\ldots,G_k)\text{ is a $k$-decomposition of }K_n\right\}.

Thus χ0(k;Kn)=ω(k;Kn)\chi_0(k;K_n)=\omega(k;K_n) and χk(k;Kn)=χ(k;Kn)\chi_k(k;K_n)=\chi(k;K_n). Mixed decomposition conjecture. Let mm and n1n\geq 1 be non-negative integers. Then

χm(k;Kn)n+(k2)for all km.\chi_m(k;K_n)\leq n+{k\choose 2}\quad\text{for all }k\geq m.

The source states that this bound for a given mm holds if and only if Plesník's conjecture holds for k=mk=m, so it packages the chromatic decomposition conjecture into a family of mixed chromatic-clique bounds.

Sources & referencesView supporting material

Primary source

Landon Rabern, “Some bounds on convex combinations of ω and χ for decompositions into many parts”, arXiv:math/0512291 (2006).

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.