On the odd cycles of normal graphs

DOI10.1016/S0166-218X(99)00018-9MaRDI QIDQ1293197zbMATH OpenFDO

Authors Caterina De Simone, János Körner

Publication date 2 January 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(99)00018-9

zbMATH Keywords

normal graphperfect graphstrong perfect graph conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

• Disproving the normal graph conjecture
• The normal graph conjecture for classes of sparse graphs
• The normal graph conjecture for two classes of sparse graphs
• The normal graph conjecture is true for circulants
• Verification of the normal graph conjecture on particular classes of graphs

Cites work

• Entropy splitting for antiblocking corners and perfect graphs
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3453665 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• Two-step encoding for finite sources

Cited in

(13)

• Constructions for normal graphs and some consequences
• The normal graph conjecture for two classes of sparse graphs
• Some bounds of weighted entropies with augmented Zagreb index edge weights
• Disproving the normal graph conjecture
• Almost all regular graphs are normal
• Minimal normal graph covers
• Line-graphs of cubic graphs are normal
• Normal hypergraphs and the perfect graph conjecture. (Reprint)
• The normal graph conjecture for classes of sparse graphs
• Verification of the normal graph conjecture on particular classes of graphs
• The normal graph conjecture is true for circulants
• On equistable, split, CIS, and related classes of graphs
• On digraphs with the odd cycle property

This page was built for publication: On the odd cycles of normal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1293197)