De Joannis de Verclos–Kang–Pastor conjecture for squares of claw-free graphs

From papers

Let GG be a claw-free graph, meaning that GG has no induced subgraph isomorphic to the complete bipartite graph K1,3K_{1,3}. Let G2G^2 be the graph obtained from GG by adding an edge between every pair of vertices joined by a two-edge path, and let ω(G)\omega(G) and χ(G2)\chi(G^2) denote its clique and chromatic numbers, respectively.

De Joannis de Verclos–Kang–Pastor conjecture. For any claw-free graph GG,

χ(G2)14(5ω(G)22ω(G)+1)\chi(G^2) \leq \frac14(5\omega(G)^2 -2\omega(G)+1)

if ω(G)\omega(G) is odd, and

χ(G2)54ω(G)2\chi(G^2) \leq \frac54\omega(G)^2

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

No solutions have been posted yet.