Choudum–Karthick–Shalu conjecture on quadratic coloring of P5P_5-free graphs

About 4 years old · traced to

For a graph GG, let χ(G)\chi(G) denote its chromatic number and ω(G)\omega(G) its clique number. A graph is P5P_5-free if it has no induced subgraph isomorphic to the five-vertex path P5P_5. Choudum–Karthick–Shalu conjecture. There exists a constant cc such that for every P5P_5-free graph GG,

χ(G)≤cω2(G).\chi(G)\le c\omega^2(G).

The conjecture proposes a quadratic binding function for the class of P5P_5-free graphs and is stated in the source as still open.

References

Primary source

Di Wu and Baogang Xu, “Coloring_of_some_crown-free_graphs”, arXiv:2307.11946 (2023).

Additional references

2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2205.08291.

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.