Disproving the normal graph conjecture

DOI10.1016/J.JCTB.2020.04.001MaRDI QIDQ2222050zbMATH OpenOpenAlexFDO

Authors Ararat Harutyunyan, Lucas Pastor, Stéphan Thomassé

Publication date 3 February 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

random graphsprobabilistic methodperfect graphsnormal graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Perfect graphs (05C17) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: A graph $G$ is called normal if there exist two coverings, $mathbbC$ and $mathbbS$ of its vertex set such that every member of $mathbbC$ induces a clique in $G$, every member of $mathbbS$ induces an independent set in $G$ and $CcapSeqemptyset$ for every $CinmathbbC$ and $SinmathbbS$. It has been conjectured by De Simone and K"orner in 1999 that a graph $G$ is normal if $G$ does not contain $C_5$, $C_7$ and $overline{C}_7$ as an induced subgraph. We disprove this conjecture.

Recommendations

• Verification of the normal graph conjecture on particular classes of graphs
• Disproof of a conjecture in graph reconstruction theory
• The normal graph conjecture is true for circulants
• scientific article; zbMATH DE number 3893229
• The normal graph conjecture for classes of sparse graphs
• The normal graph conjecture is true for minimal unbreakable graphs
• The normal graph conjecture for two classes of sparse graphs
• Disproving a conjecture on PI-index of graphs
• A disproof of Henning's conjecture on irredundance perfect graphs
• Normal hypergraphs and the perfect graph conjecture. (Reprint)

Cites work

• scientific article; zbMATH DE number 3468645 (Why is no real title available?)
• scientific article; zbMATH DE number 3453665 (Why is no real title available?)
• Almost all regular graphs are normal
• Entropy splitting for antiblocking corners and perfect graphs
• Graph imperfection and channel assignment
• Graph imperfection. I
• Graph imperfection. II
• Graphs that Split Entropies
• Line-graphs of cubic graphs are normal
• On the independence number of random graphs
• On the odd cycles of normal graphs
• Perfect graphs and graph entropy: An updated survey
• Probability and Computing
• The normal graph conjecture for classes of sparse graphs
• The normal graph conjecture is true for circulants
• Two-step encoding for finite sources

Cited in

(9)

• Line-graphs of cubic graphs are normal
• Almost all regular graphs are normal
• Verification of the normal graph conjecture on particular classes of graphs
• Constructions for normal graphs and some consequences
• Minimal normal graph covers
• The normal graph conjecture for two classes of sparse graphs
• The normal graph conjecture is true for minimal unbreakable graphs
• The normal graph conjecture is true for circulants
• The normal graph conjecture for classes of sparse graphs

This page was built for publication: Disproving the normal graph conjecture

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