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

normal graphsperfect graphsprobabilistic methodrandom graphs

Mathematics Subject Classification ID

Perfect graphs (05C17) 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) Random graphs (graph-theoretic aspects) (05C80) 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

• 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
• scientific article; zbMATH DE number 3468645 (Why is no real title available?)
• scientific article; zbMATH DE number 3453665 (Why is no real title available?)
• 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

(10)

• Constructions for normal graphs and some consequences
• On the odd cycles of normal graphs
• The normal graph conjecture for two classes of sparse graphs
• Almost all regular graphs are normal
• Minimal normal graph covers
• Line-graphs of cubic graphs are normal
• 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 minimal unbreakable graphs
• The normal graph conjecture is true for circulants

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)