Star-cutsets and perfect graphs
From MaRDI portal
DOI10.1016/0095-8956(85)90049-8zbMATH Open0674.05058OpenAlexW1965570465WikidataQ56430118 ScholiaQ56430118MaRDI QIDQ1121289FDOQ1121289
Authors: S. H. Smith 
Publication date: 1985
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(85)90049-8
Recommendations
Cites Work
- Decomposition of regular matroids
- Normal hypergraphs and the perfect graph conjecture
- Title not available (Why is that?)
- Compositions for perfect graphs
- Title not available (Why is that?)
- Combinatorial designs related to the strong perfect graph conjecture
- Critical perfect graphs and perfect 3-chromatic graphs
- Title not available (Why is that?)
- On the perfect graph conjecture
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Meyniel graphs are strongly perfect
- Graphical properties related to minimal imperfection
- Generating weakly triangulated graphs
Cited In (only showing first 100 items - show all)
- Two-colourings that decompose perfect graphs
- Title not available (Why is that?)
- Counterexamples to three conjectures concerning perfect graphs
- Addendum to: M. Conforti and M. R. Rao, ``Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets, Discrete Mathematics 104 (1992) 23--47
- Matrix partitions of perfect graphs
- On Roussel-Rubio-type lemmas and their consequences
- Graph partitions with prescribed patterns
- Operator decomposition of graphs and the reconstruction conjecture
- The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
- The polynomial dichotomy for three nonempty part sandwich problems
- POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
- Path parity and perfection
- An approach to solving \(A^{k}=J-I\)
- Decomposition of perfect graphs
- Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets
- On slim graphs, even pairs, and star-cutsets
- Galaxy cutsets in graphs
- Colouring, constraint satisfaction, and complexity
- A new property of critical imperfect graphs and some consequences
- Bull-free Berge graphs are perfect
- The strong perfect graph conjecture for pan-free graphs
- Coloring the cliques of line graphs
- On the structure of certain intersection graphs
- Quasi-star-cutsets and some consequences
- Even pairs in Berge graphs
- Odd cycles and matrices with integrality properties
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- Two classes of perfect graphs
- Novel evolutionary models and applications to sequence alignment problems
- On Some Properties of the Struction of a Graph
- Skeletal graphs - a new class of perfect graphs
- Matrix Partitions with Finitely Many Obstructions
- Stable skew partition problem
- Discs in unbreakable graphs
- Complete description of forbidden subgraphs in the structural domination problem
- Weakly triangulated graphs
- Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
- The external constraint 4 nonempty part sandwich problem
- Dominating cliques in \(P_ 5\)-free graphs
- 3-colouring AT-free graphs in polynomial time
- Chair-free Berge graphs are perfect
- \(2K_2\)-partition of some classes of graphs
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
- On edge perfectness and classes of bipartite graphs
- Substitution and \(\chi\)-boundedness
- Extended skew partition problem
- A semi-strong perfect graph theorem
- The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
- New classes of Berge perfect graphs
- Decomposing Berge graphs and detecting balanced skew partitions
- Algorithms for maximum weight induced paths
- Skew partition sandwich problem is NP-complete
- Amalgams and \(\chi\)-boundedness
- 2K2-Partition Problem
- Classes of perfect graphs
- Perfectly contractile graphs
- Simplicial decompositions of graphs: A survey of applications
- The sandwich problem for decompositions and almost monotone properties
- Fast Skew Partition Recognition
- Colouring perfect graphs with bounded clique number
- Recognizing bull-free perfect graphs
- On a conjecture about uniquely colorable perfect graphs
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Even-hole-free graphs. I: Decomposition theorem
- Square-free perfect graphs.
- FindingH-partitions efficiently
- The polynomial dichotomy for three nonempty part sandwich problems
- On the linear extension complexity of stable set polytopes for perfect graphs
- Powers of distance-hereditary graphs
- Combinatorial optimization with 2-joins
- All variations on perfectly orderable graphs
- Slim graphs
- Some properties of minimal imperfect graphs
- The perfection and recognition of bull-reducible Berge graphs
- Obstructions to partitions of chordal graphs
- On a class of square-free graphs
- Forbidden lifts (NP and CSP for combinatorialists)
- Alternating orientation and alternating colouration of perfect graphs
- Even-hole-free graphs part II: Recognition algorithm
- About skew partitions in minimal imperfect graphs
- List matrix partitions of chordal graphs
- No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
- Bull-Reducible Berge Graphs are Perfect
- On the structure of self-complementary graphs
- On the strong perfect graph conjecture
- Join colourings of chordal graphs
- A reduction procedure for coloring perfect \(K_ 4\)-free graphs
- Murky graphs
- Burling graphs revisited. II: Structure
- Cutsets in perfect and minimal imperfect graphs
- Quasi-parity and perfect graphs
- Locally perfect graphs
- Wings and perfect graphs
- A class of perfect graphs containing \(P_{6}\)
- Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
- A new class of perfect Hoàng graphs
- On the \(P_ 4\)-structure of perfect graphs. III: Partner decompositions
- Disjoint clique cutsets in graphs without long holes
- \(P_4\)-domination in minimal imperfect graphs
- On minimal imperfect graphs without induced \(P_5\)
This page was built for publication: Star-cutsets and perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121289)
