×

On the odd cycles of normal graphs. (English) Zbl 0928.05035

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.

MSC:

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

References:

[1] Berge, C., Sur une conjecture relative au problème des codes optimaux, Comm (1962), 13ème assemblée générale de l’URSI: 13ème assemblée générale de l’URSI Tokyo
[2] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[3] Csiszár, I.; Körner, J.; Lovász, L.; Marton, K.; Simonyi, G., Entropy splitting for anti-blocking corners and perfect graphs, Combinatorica, 10, 27-40 (1990) · Zbl 0734.05061
[4] Körner, J., An extension of the class of perfect graphs, Studia Math. Hung., 8, 405-409 (1973) · Zbl 0289.05132
[5] Körner, J.; Longo, G., Two-step encoding of finite memoryless sources, IEEE Trans. Inform. Theory, 19, 778-782 (1973) · Zbl 0278.94011
[6] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253-267 (1972) · Zbl 0239.05111
[7] Shannon, C. E., The zero-error capacity of a noisy channel, IRE Trans. Inform. Theory, 2, 8-19 (1956)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.