On the odd cycles of normal graphs (Q1293197): Difference between revisions

A graph \(G = (V,E)\) is normal if there is a clique cover \({\mathcal C}\) and a stable set cover \({\mathcal S}\) of \(V\) such that every \(C \in\) \({\mathcal C}\) intersects every \(S \in\) \({\mathcal S}\). The authors note the similarity of normal graphs to perfect graphs (e.g., every perfect graph is normal) and pose a problem like Berge's strong perfect graph conjecture: Are the only minimally non-normal graphs \(C_5\), \(C_7\) and \(\overline C_7\)? The authors provide a sufficiency condition for a graph to be normal, in terms of minimal edge covers.