De Joannis de Verclos–Kang–Pastor conjecture for squares of claw-free graphs
De Joannis de Verclos–Kang–Pastor conjecture for squares of claw-free graphs
Let be a claw-free graph, meaning that has no induced subgraph isomorphic to the complete bipartite graph . Let be the graph obtained from by adding an edge between every pair of vertices joined by a two-edge path, and let and denote its clique and chromatic numbers, respectively.
De Joannis de Verclos–Kang–Pastor conjecture. For any claw-free graph ,
if is odd, and
otherwise.
This conjecture strengthens the Erdős–Nešetřil conjecture from line graphs to all claw-free graphs. The source describes it as a conjecture; the supplied status is unknown, so its resolution is not established here.
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
Wouter Cames van Batenburg and Ross J. Kang, “Squared chromatic number without claws or large cliques”, arXiv:1609.08646 (2018).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.