Extremal sum-color cost conjecture for k-trees

A kk-tree is a graph obtained from KkK_k by iteratively adding a vertex whose neighborhood is a kk-clique in the existing graph. The join GHG\vee H is obtained from the disjoint union G+HG+H by making every vertex in GG adjacent to every vertex in HH. The kkth power PnkP_n^k of the path PnP_n has the same vertex set as PnP_n, with two vertices adjacent exactly when their distance in PnP_n is at most kk. For kNk\in\mathbb{N}, let TT be a kk-tree with nn vertices, and let \mathaccent"017s(G)\operatorname{\mathaccent"017{s}}(G) denote the sum-color cost of a graph GG. Extremal sum-color cost conjecture for kk-trees.

\mathaccent"017s(KkKnk)\mathaccent"017s(T)\mathaccent"017s(Pnk).\operatorname{\mathaccent"017{s}}(K_k\vee \overline{K}_{n-k})\leq\operatorname{\mathaccent"017{s}}(T)\leq\operatorname{\mathaccent"017{s}}(P_n^k).

This extends the proved extremal result for trees, with the split graph KkKnkK_k\vee\overline{K}_{n-k} conjectured to minimize and the kkth power of the path conjectured to maximize the sum-color cost among nn-vertex kk-trees. The claim is presented as a conjecture, and no resolution is given in the source.

Sources & referencesView supporting material

Primary source

Thomas Mahoney, Gregory J. Puleo and Douglas B. West, “Online Paintability: The Slow-Coloring Game”, arXiv:1507.06513 (2017).

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.