De Simone–Körner conjecture on hereditary normality of graphs

Let GG be a graph. A graph is hereditarily normal if every induced subgraph of GG 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 GG is hereditarily normal if and only if neither GG 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

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.