Star-cutsets and perfect graphs

DOI10.1016/0095-8956(85)90049-8zbMath0674.05058OpenAlexW1965570465WikidataQ56430118 ScholiaQ56430118MaRDI QIDQ1121289

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

zbMATH Keywords

perfect graphs Meyniel graphs perfectly orderable graphs star-cutset

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Related Items

Fast Skew Partition Recognition, Burling graphs revisited. II: Structure, Computation in Causal Graphs, The polynomial dichotomy for three nonempty part sandwich problems, The polynomial dichotomy for three nonempty part sandwich problems, On the strong perfect graph conjecture, Disjoint clique cutsets in graphs without long holes, FindingH-partitions efficiently, The perfection and recognition of bull-reducible Berge graphs, Unnamed Item, Unnamed Item, New classes of Berge perfect graphs, Most unbreakable murky graphs are bull-free, POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM, Alternating orientation and alternating colouration of perfect graphs, Stable skew partition problem, On the density of trigraph homomorphisms, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Even and odd pairs in linegraphs of bipartite graphs, Bull-free Berge graphs are perfect, A reduction procedure for coloring perfect \(K_ 4\)-free graphs, On the structure of certain intersection graphs, Quasi-parity and perfect graphs, Recognizing bull-free perfect graphs, On a class of square-free graphs, Murky graphs, Path parity and perfection, Perfect graphs with unique \(P_ 4\)-structure, Discs in unbreakable graphs, Two-colourings that decompose perfect graphs, Powers of distance-hereditary graphs, A new class of perfect Hoàng graphs, A semi-strong perfect graph theorem, A new property of critical imperfect graphs and some consequences, Locally perfect graphs, Building counterexamples, Colouring perfect graphs with bounded clique number, Novel evolutionary models and applications to sequence alignment problems, Two classes of perfect graphs, The strong perfect graph conjecture for pan-free graphs, Wings and perfect graphs, On edge perfectness and classes of bipartite graphs, All variations on perfectly orderable graphs, On a Class of P ₅ -Free Graphs, Coloring the cliques of line graphs, Simplicial decompositions of graphs: A survey of applications, Chair-free Berge graphs are perfect, On a conjecture about uniquely colorable perfect graphs, Slim graphs, On the \(P_ 4\)-structure of perfect graphs. III: Partner decompositions, Some properties of minimal imperfect graphs, Obstructions to partitions of chordal graphs, 3-colouring AT-free graphs in polynomial time, Amalgams and χ-Boundedness, Forbidden lifts (NP and CSP for combinatorialists), Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs, A class of perfect graphs containing \(P_{6}\), Extended skew partition problem, Matrix partitions of perfect graphs, Classes of perfect graphs, An approach to solving \(A^{k}=J-I\), Colouring, constraint satisfaction, and complexity, Substitution and \(\chi\)-boundedness, Square-free perfect graphs., Short-chorded and perfect graphs, Dominating cliques in \(P_ 5\)-free graphs, Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs, Decomposing Berge graphs and detecting balanced skew partitions, Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets, Counterexamples to three conjectures concerning perfect graphs, On slim graphs, even pairs, and star-cutsets, Operator decomposition of graphs and the reconstruction conjecture, The external constraint 4 nonempty part sandwich problem, The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem, On Roussel-Rubio-type lemmas and their consequences, \(2K_2\)-partition of some classes of graphs, The P versus NP-complete dichotomy of some challenging problems in graph theory, Skew partitions in perfect graphs, The strong perfect graph conjecture holds for diamonded odd cycle-free graphs, Galaxy cutsets in graphs, Even-hole-free graphs part I: Decomposition theorem, The sandwich problem for cutsets: clique cutset, \(k\)-star cutset, Graph partitions with prescribed patterns, Join colourings of chordal graphs, Even pairs in Berge graphs, The sandwich problem for decompositions and almost monotone properties, A generalization of Chvátal's star-cutset lemma, Complete description of forbidden subgraphs in the structural domination problem, On the linear extension complexity of stable set polytopes for perfect graphs, Odd cycles and matrices with integrality properties, Combinatorial optimization with 2-joins, Decomposition of odd-hole-free graphs by double star cutsets and 2-joins, Skew partition sandwich problem is NP-complete, On minimal imperfect graphs without induced \(P_5\), \(P_4\)-domination in minimal imperfect graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Defending Planar Graphs against Star-Cutsets, About skew partitions in minimal imperfect graphs, No odd pairs in minimal imperfect NP\({}_{5}\) graphs., Weakly triangulated graphs, Perfectly contractile graphs, Bull-Reducible Berge Graphs are Perfect, On the structure of self-complementary graphs, 2K2-Partition Problem, Matrix Partitions with Finitely Many Obstructions, Quasi-star-cutsets and some consequences, A faster algorithm to recognize even-hole-free graphs, Algorithms for maximum weight induced paths, Decomposition of perfect graphs, Even-hole-free graphs part II: Recognition algorithm, List matrix partitions of chordal graphs

Cites Work