Perfect-or-bounded-clique-width conjecture for claw-, -, and bridge-free graphs
Perfect-or-bounded-clique-width conjecture for claw-, -, and bridge-free graphs
Let be a -free graph.
Perfect-or-bounded-clique-width conjecture. One of the following holds:
- is perfect.
- has bounded clique-width.
The conjecture would remove the -twin restriction from the paper's polynomial-time colouring result by establishing bounded clique-width whenever such a graph is not perfect. Its status is open in the source.
Sources & referencesView supporting material
Primary source
Kathie Cameron, Chính T. Hoàng and Taite LaGrange, “On graphs without four-vertex induced subgraphs”, arXiv:2505.00202 (2025).
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
Sign in to submit a solution.
No solutions have been posted yet.