Publication:4238043
From MaRDI portal
DOI<289::AID-JGT4>3.0.CO;2-3 10.1002/(SICI)1097-0118(199904)30:4<289::AID-JGT4>3.0.CO;2-3zbMath0920.05028MaRDI QIDQ4238043
Cornuéjols, Gérard, Michele Conforti, Ajai Kapoor, Kristina Vušković
Publication date: 26 May 1999
cap; decomposition; testing; strong perfect graph conjecture; Meyniel graphs; odd holes; chordless cycle; \(\beta\)-perfect graphs; cap-free graphs; even-signable and odd-signable graphs; polynomial recognition algorithms
05C75: Structural characterization of families of graphs
05C15: Coloring of graphs and hypergraphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, A structure theorem for graphs with no cycle with a unique chord and its consequences, Recognition of quasi-Meyniel graphs, Triangulated neighborhoods in even-hole-free graphs, Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences, Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs, Even-hole-free graphs part I: Decomposition theorem, Graphs of Separability at Most Two: Structural Characterizations and Their Consequences, Even-hole-free graphs part II: Recognition algorithm