De Simone–Körner conjecture on hereditary normality of graphs
De Simone–Körner conjecture on hereditary normality of graphs
Let be a graph. A graph is hereditarily normal if every induced subgraph of is normal, where a graph is normal when it has coverings by cliques and stable sets such that every clique in one covering intersects every stable set in the other. An induced subgraph is a 5-cycle or 7-cycle when it is isomorphic to the corresponding cycle graph.
De Simone–Körner conjecture. A graph is hereditarily normal if and only if neither nor its complement contains a 5-cycle or a 7-cycle as an induced subgraph.
The conjecture aims to characterize hereditary normality by the two known minimal obstructions, the 5-cycle, the 7-cycle, and the complement of the 7-cycle. The source gives no resolution status.
Sources & referencesView supporting material
Primary source
Zsolt Patakfalvi, “Line-graphs of cubic graphs are normal”, arXiv:math/0605568 (2006).
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
Sign in to submit a solution.
No solutions have been posted yet.