Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949518 | Discrete Applied Mathematics | 2017 | 5 Pages |
Abstract
In 1999, De Simone and Körner conjectured that every graph without induced C5,C7,C¯7 contains a clique cover C and a stable set cover I such that every clique in C and every stable set in I 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 C4-free graphs of bounded maximum degree and sufficiently large odd girth (linear in the maximum degree) are normal. This is used to prove that for every fixed d, random d-regular graphs are a.a.s. normal.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Seyed Saeed Changiz Rezaei, Seyyed Aliasghar Hosseini, Bojan Mohar,