Conjecture on minimally _g-imperfect graphs

About 7 years old · traced to

Let GG be a graph. It is minimally γg\gamma_g-imperfect if GG is not γg\gamma_g-perfect, while every proper induced subgraph of GG is γg\gamma_g-perfect. The anti-holes Cn‾\overline{C_n} for n≥5n\geq 5, together with the eight additional graphs listed in Proposition~, are the graphs under consideration. Classification conjecture. There are no other minimally γg\gamma_g-imperfect graphs but those listed in Proposition~. This conjecture is based on computer verification for graphs with at most nine vertices and on the paper's structural results for connected and triangle-free imperfect graphs; its status beyond those verified cases remains open.

References

Primary source

Csilla Bujtás, Vesna Iršič and Sandi Klavžar, “Perfect graphs for domination games”, arXiv:1908.09513 (2019).

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.