The normal graph conjecture for two classes of sparse graphs

DOI10.1007/S00373-017-1868-2zbMATH Open1382.05039OpenAlexW2781165376WikidataQ123003097 ScholiaQ123003097MaRDI QIDQ1706428FDOQ1706428

Authors: Anne Berry, Annegret K. Wagler 

Publication date: 22 March 2018

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-017-1868-2

Recommendations

• The normal graph conjecture for classes of sparse graphs
• Verification of the normal graph conjecture on particular classes of graphs
• scientific article; zbMATH DE number 3893229
• Constructions for normal graphs and some consequences
• Normal hypergraphs and the perfect graph conjecture. (Reprint)
• The \(1,2,3\)-conjecture and \(1,2\)-conjecture for sparse graphs
• The normal graph conjecture is true for circulants
• The normal graph conjecture is true for minimal unbreakable graphs
• The norms of graph spanners
• Disproving the normal graph conjecture

zbMATH Keywords

cacti1-treesnormal graph conjecture

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42) Perfect graphs (05C17)

Cites Work

• The strong perfect graph theorem
• Algorithmic Aspects of Vertex Elimination on Graphs
• Constructions for normal graphs and some consequences
• On the odd cycles of normal graphs
• The normal graph conjecture for classes of sparse graphs
• Graphs that Split Entropies
• The normal graph conjecture is true for circulants
• Two-step encoding for finite sources
• Title not available (Why is that?)
• Entropy splitting for antiblocking corners and perfect graphs
• Perfect graphs and graph entropy: An updated survey
• Almost all Berge Graphs are Perfect
• Disproving the normal graph conjecture

Cited In (9)

• Disproving the normal graph conjecture
• Line-graphs of cubic graphs are normal
• Verification of the normal graph conjecture on particular classes of graphs
• Almost all regular graphs are normal
• Constructions for normal graphs and some consequences
• Minimal normal graph covers
• 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: The normal graph conjecture for two classes of sparse graphs

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