A new conjecture about minimal imperfect graphs

DOI10.1016/0095-8956(89)90024-5zbMATH Open0634.05048OpenAlexW2092861584MaRDI QIDQ1096648FDOQ1096648

B. George

Publication date: 1989

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://digitalcommons.odu.edu/cgi/viewcontent.cgi?article=1111&context=computerscience_fac_pubs

Recommendations

• Some properties of minimal imperfect graphs
• Counterexamples to three conjectures concerning perfect graphs
• Some aspects of minimal imperfect graphs
• On critical edges in minimal imperfect graphs
• Even pairs and the strong perfect graph conjecture

zbMATH Keywords

pathperfect graphschordless patheven number of edgesminimal imperfect graphsodd number of edges

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph theory (05C99)

Cites Work

• A new property of critical imperfect graphs and some consequences
• A note on even pairs

Cited In (13)

• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• Some aspects of minimal imperfect graphs
• Path parity and perfection
• Title not available (Why is that?)
• Quasi-star-cutsets and some consequences
• \(P_4\)-domination in minimal imperfect graphs
• Even and odd pairs in linegraphs of bipartite graphs
• Graph Imperfection with a Co-Site Constraint
• New tools and results in graph minor structure theory
• On vertex neighborhood in minimal imperfect graphs
• Polyhedral results on the stable set problem in graphs containing even or odd pairs
• Some properties of minimal imperfect graphs
• About skew partitions in minimal imperfect graphs

This page was built for publication: A new conjecture about minimal imperfect graphs

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