Discs in unbreakable graphs

DOI10.1007/BF01793011MaRDI QIDQ1900520zbMATH OpenOpenAlexFDO

Authors Ryan Hayward

Publication date 11 March 1996

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

Full work available at URL https://doi.org/10.1007/bf01793011

zbMATH Keywords

chordless cyclediscperfect graphunbreakable graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

A graph \(G\) is said to be unbreakable if it has at least three vertices and neither the graph nor its complement has a star cutset (i.e., a non- empty subset \(C\) of the vertices of \(G\), for which \(G- C\) is disconnected and some vertex of \(C\) is adjacent to all other vertices of \(C\)). In this paper it is shown that every vertex in an unbreakable graph is in a disc, where a disc is a chordless cycle, or the complement of a chordless cycle, with at least five vertices. A corollary is that every vertex in a minimal imperfect graph is in a disc.

Recommendations

• A NEW CHARACTERIZATION OF UNBREAKABLE GRAPHS
• On the structure of unbreakable graphs
• The unbreakable frame matroids
• Murky graphs
• Wings and perfect graphs

Cites work

• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• Star-cutsets and perfect graphs
• Topics on perfect graphs
• Weakly triangulated graphs

Cited in

(9)

• Murky graphs
• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• A new class of perfect Hoàng graphs
• Bull-Reducible Berge Graphs are Perfect
• scientific article; zbMATH DE number 4079463 (Why is no real title available?)
• On the structure of unbreakable graphs
• A NEW CHARACTERIZATION OF UNBREAKABLE GRAPHS
• The perfection and recognition of bull-reducible Berge graphs
• On Roussel-Rubio-type lemmas and their consequences

This page was built for publication: Discs in unbreakable graphs

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