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.
References
- Wouter Cames van Batenburg and Ross J. Kang, “Squared chromatic number without claws or large cliques”, arXiv:1609.08646 (2018).
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
No solutions have been posted yet.