← All problems

The Normal Graph Conjecture

13 years old · traced to

Let GG be a graph. A graph is normal if its vertex set has coverings by cliques and by independent sets such that every clique in the first covering intersects every independent set in the second. Let CkC_k denote the cycle on kk vertices, and let C7‾\overline{C_7} denote its complement. The Normal Graph Conjecture. If GG has no C5C_5, C7C_7 or C7‾\overline{C_7} as an induced subgraph, then GG is normal.

References

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

Status

Source: Ararat Harutyunyan, Lucas Pastor and Stéphan Thomassé, “Disproving the normal graph conjecture”, arXiv:1508.05487 (2020).

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.