Disproving the normal graph conjecture

DOI10.1016/j.jctb.2020.04.001zbMath1458.05213arXiv1508.05487OpenAlexW3017092182MaRDI QIDQ2222050

Lucas Pastor, Ararat Harutyunyan, Steé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 graphsperfect graphsprobabilistic methodnormal graphs

Mathematics Subject Classification ID

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

Related Items (1)

The normal graph conjecture for two classes of sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Entropy splitting for antiblocking corners and perfect graphs
• On the independence number of random graphs
• On the odd cycles of normal graphs
• Graph imperfection. I
• Graph imperfection. II
• Almost all regular graphs are normal
• Line-graphs of cubic graphs are normal
• The Normal Graph Conjecture for Classes of Sparse Graphs
• Graphs that Split Entropies
• Two-step encoding for finite sources
• Probability and Computing

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