The Normal Graph Conjecture
Let 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 denote the cycle on vertices, and let denote its complement. The Normal Graph Conjecture. If has no , or as an induced subgraph, then 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
- Refuted: Ararat Harutyunyan, Lucas Pastor, and Stéphan Thomassé. Disproving the normal graph conjecture (Journal of Combinatorial Theory, Series B, 2020) https://doi.org/10.1016/j.jctb.2020.04.001
Source: Ararat Harutyunyan, Lucas Pastor and Stéphan Thomassé, “Disproving the normal graph conjecture”, arXiv:1508.05487 (2020).
Progress summary
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.