Extremal sum-color cost conjecture for k-trees
Extremal sum-color cost conjecture for k-trees
A -tree is a graph obtained from by iteratively adding a vertex whose neighborhood is a -clique in the existing graph. The join is obtained from the disjoint union by making every vertex in adjacent to every vertex in . The th power of the path has the same vertex set as , with two vertices adjacent exactly when their distance in is at most . For , let be a -tree with vertices, and let denote the sum-color cost of a graph . Extremal sum-color cost conjecture for -trees.
This extends the proved extremal result for trees, with the split graph conjectured to minimize and the th power of the path conjectured to maximize the sum-color cost among -vertex -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.