A characterization of perfect graphs
From MaRDI portal
Publication:2553372
DOI10.1016/0095-8956(72)90045-7zbMath0241.05107OpenAlexW2076086747WikidataQ55869627 ScholiaQ55869627MaRDI QIDQ2553372
Publication date: 1972
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(72)90045-7
Related Items
Covering Regions with Squares, A characterization of claw-free CIS graphs and new results on the order of CIS graphs, The story of perfectly orderable graphs, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs, Coloring all directed paths in a symmetric tree, with an application to optical networks, Eternal domination and clique covering, Coloring graph classes with no induced fork via perfect divisibility, Structural properties of Toeplitz graphs, ?-Perfect graphs, Properties of Large 2-Crossing-Critical Graphs, On perfect graphs and polyhedra with (0, 1)-valued extreme points, Minimal imperfect graphs: A simple approach, Minimum weighted clique cover on claw‐free perfect graphs, On graphs with no induced five‐vertex path or paraglider, Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration, Chordal and perfect zero-divisor graphs of posets and applications to graphs associated with algebraic structures, Polynomial Kernel for Interval Vertex Deletion, Problems and results on 1-cross-intersecting set pair systems, A Sum of Squares Characterization of Perfect Graphs, The clique problem with multiple-choice constraints under a cycle-free dependency graph, Problems close to my heart, On chromatic number and perfectness of fuzzy graph, Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs, Hitting all maximum stable sets in \(P_5\)-free graphs, Perfect graphs, kernels, and cores of cooperative games, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, Precoloring Extension III: Classes of Perfect Graphs, The linear guessing number of undirected graphs, The maximum vertex coverage problem on bipartite graphs, Random perfect graphs, On circular-perfect graphs: a survey, Stable effectivity functions and perfect graphs, Forced color classes, intersection graphs and the strong perfect graph conjecture, Combinatorial symbolic powers, Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs, STRONG KOSZULNESS OF TORIC RINGS ASSOCIATED WITH STABLE SET POLYTOPES OF TRIVIALLY PERFECT GRAPHS, A note on even pairs, On classes of minimal circular-imperfect graphs, On the strong perfect graph conjecture, Line perfect graphs, Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint), Complexity classification of some edge modification problems, C-perfect hypergraphs, On kernel-less clique-acyclic orientations of minimally imperfect graphs, Independent sets and hitting sets of bicolored rectangular families, Maximal ambiguously \(k\)-colorable graphs, Norms and perfect graphs, Claw-free circular-perfect graphs, On the linear extension complexity of stable set polytopes for perfect graphs, Modular decomposition of graphs and the distance preserving property, Square-Free Graphs with No Six-Vertex Induced Path, Edmonds polytopes and a hierarchy of combinatorial problems, Improper sum-list colouring of 2-trees, Chordal 2‐Connected Graphs and Spanning Trees, THE CHARACTER GRAPH OF A FINITE GROUP IS PERFECT, Finite checkability for integer rounding properties in combinatorial programming problems, Miscellaneous Digraph Classes, A new characterization of trivially perfect graphs, Submodular functions and rooted trees, Perfect zero–one matrices, On the interval chromatic number of proper interval graphs, Point partition numbers: perfect graphs, Near-perfect matrices, New classes of Berge perfect graphs, A note on clutter partitions, Perfect graphs with no \(P_ 5\) and no \(K_ 5\), Finite-type invariants for graphs and graph reconstructions, New classes of perfect graphs, An extension of Lehman's theorem and ideal set functions, Mock threshold graphs, A reduction procedure for coloring perfect \(K_ 4\)-free graphs, Generalized perfect graphs: Characterizations and inversion, Quasi-parity and perfect graphs, Motivations and history of some of my conjectures, On transversals in minimal imperfect graphs, Perfect graphs with unique \(P_ 4\)-structure, A new property of critical imperfect graphs and some consequences, Locally perfect graphs, Building counterexamples, Fractional kernels in digraphs, Wings and perfect graphs, Duality and perfection for edges in cliques, Opposition graphs are strict quasi-parity graphs, Forbidden graphs for degree and neighbourhood conditions, Chair-free Berge graphs are perfect, On a conjecture about uniquely colorable perfect graphs, On essential components and critical sets of a graph, Computing clique and chromatic number of circular-perfect graphs in polynomial time, Perfect graphs are kernel solvable, The structure of imperfect critically strongly-imperfect graphs, Graph models for scheduling systems with machine saturation property, Graphical properties related to minimal imperfection, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, Zur Theorie der perfekten Graphen, On certain polytopes associated with graphs, The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy, Entropy of symmetric graphs, Star coloring of certain graph classes, Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs, Wide partitions, Latin tableaux, and Rota's basis conjecture, The strong perfect graph conjecture for toroidal graphs, A classification of certain graphs with minimal imperfection properties, Finding a maximum independent set in a permutation graph, On the strong perfect graph conjecture and critical graphs, A survey of the algorithmic aspects of modular decomposition, On stable set polyhedra for K//(1,3)free graphs, Coloring graphs with stable cutsets, Vertex-transitive CIS graphs, Short-chorded and perfect graphs, Perfect graph decompositions, Perfect graphs and norms, Handelman's hierarchy for the maximum stable set problem, Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, Sum-perfect graphs, Perfect \(0,\pm 1\) matrices, On the complexity of bandwidth allocation in radio networks, Preperfect graphs, Optimal parallel time bounds for the maximum clique problem on intervals, Counterexamples to three conjectures concerning perfect graphs, On generalized perfect graphs: Bounded degree and bounded edge perfection, Perfect commuting graphs, Not complementary connected and not CIS \(d\)-graphs form weakly monotone families, Decomposing complete edge-chromatic graphs and hypergraphs. Revisited, Antitwins in partitionable graphs, The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs, Some remarks on Hajós' conjecture, A class of facet producing graphs for vertex packing polyhedra, Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs, Chromatic bounds for some classes of \(2 K_2\)-free graphs, Perfect graphs involving semitotal and semipaired domination, Almost integral polyhedra related to certain combinatorial optimization problems, Perfect product graphs, Critical perfect graphs and perfect 3-chromatic graphs, Trivially perfect graphs, Even pairs in Berge graphs, Perfectness of normal products of graphs, Combinatorial designs related to the strong perfect graph conjecture, Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs, A min-max relation for the partial q-colourings of a graph. II: Box perfection, Lehman matrices, Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture, Vertex- and edge-minimal and locally minimal graphs, Uniquely colorable perfect graphs, On minimal imperfect graphs without induced \(P_5\), Sequential colorings and perfect graphs, \(P_4\)-domination in minimal imperfect graphs, Brambles and independent packings in chordal graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Completeness for intersection classes, On a geometric property of perfect graphs, Graph imperfection. I, About skew partitions in minimal imperfect graphs, On circular critical graphs, A family of perfect graphs associated with directed graphs, A description of claw-free perfect graphs, On the stability number of the edge intersection of two graphs., Tolerance graphs, Non-regular square bipartite designs, On the Laplacian spectrum of (\(\alpha,\omega\))-graphs, Coloring perfect \((K_ 4\)-e)-free graphs, Some sequences associated with combinatorial structures, On the independence polynomial of the corona of graphs
Cites Work
