Plesník's chromatic decomposition conjecture for complete graphs

From papers

A kk-decomposition of the complete graph KnK_n is a decomposition into kk spanning subgraphs G1,,GkG_1,\ldots,G_k, and for a graph parameter pp let

p(k;Kn)=max{j=1kp(Gj)(G1,,Gk) is a k-decomposition of Kn}.p(k;K_n)=\max\left\{\sum_{j=1}^{k}p(G_j)\mid (G_1,\ldots,G_k)\text{ is a $k$-decomposition of }K_n\right\}.

Here χ\chi denotes chromatic number and ω\omega clique number. Plesník's conjecture. If kk and nn are positive integers, then

χ(k;Kn)n+(k2).\chi(k;K_n)\leq n+{k\choose 2}.

This would extend the known equality χ(k;Kn)=ω(k;Kn)\chi(k;K_n)=\omega(k;K_n) for k3k\leq 3 and, together with the corresponding clique-number bound, would give the best possible upper bound for convex combinations of ω\omega and χ\chi.

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

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

Solutions 0

No solutions have been posted yet.