The normal graph conjecture for two classes of sparse graphs

DOI10.1007/S00373-017-1868-2MaRDI QIDQ1706428zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

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

Cited in

(9)

• Disproving the normal graph conjecture
• 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 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)