Almost all regular graphs are normal

DOI10.1016/J.DAM.2017.07.001MaRDI QIDQ2399290zbMATH OpenOpenAlexFDO

Authors Seyed Saeed Changi Rezaei, Seyyed Aliasghar Hosseini, Bojan Mohar

Publication date 22 August 2017

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

Full work available at URL https://arxiv.org/abs/1511.07591

zbMATH Keywords

graph entropynormal graph conjecturerandom regular graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: In 1999, De Simone and K"{o}rner conjectured that every graph without induced $C_5,C_7,overline{C}_7$ contains a clique cover $mathcalC$ and a stable set cover $mathcalI$ such that every clique in $mathcalC$ and every stable set in $mathcalI$ have a vertex in common. This conjecture has roots in information theory and became known as the Normal Graph Conjecture. Here we prove that all graphs of bounded maximum degree and sufficiently large odd girth (linear in the maximum degree) are normal. This implies that for every fixed $d$, random $d$-regular graphs are a.a.s. normal.

Recommendations

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

Cites work

• Constructions for normal graphs and some consequences
• Entropy splitting for antiblocking corners and perfect graphs
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 3453665 (Why is no real title available?)
• Information theory. Coding theorems for discrete memoryless systems
• Line-graphs of cubic graphs are normal
• On the odd cycles of normal graphs
• The normal graph conjecture is true for circulants
• The normal graph conjecture is true for minimal unbreakable graphs
• Two-step encoding for finite sources
• Verification of the normal graph conjecture on particular classes of graphs

Cited in

(1)

• Disproving the normal graph conjecture

This page was built for publication: Almost all regular graphs are normal

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