Normal hypergraphs and the perfect graph conjecture
From MaRDI portal
Publication:2553445
DOI10.1016/0012-365X(72)90006-4zbMath0239.05111OpenAlexW1997998268WikidataQ55869517 ScholiaQ55869517MaRDI QIDQ2553445
Publication date: 1972
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(72)90006-4
Extremal problems in graph theory (05C35) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)
Related Items
Relaxations of vertex packing, Characterizing intersection classes of graphs, Some properties on the tensor product of graphs obtained by monogenic semigroups, Polyhedral proof methods in combinatorial optimization, A note on perfect graphs, The homogeneous set sandwich problem, A lower bound on the independence number of a graph in terms of degrees and local clique sizes, Exploring the concept of perfection in 3-hypergraphs, The pair completion algorithm for the homogeneous set sandwich problem, Bull-free Berge graphs are perfect, A reduction procedure for coloring perfect \(K_ 4\)-free graphs, On a conjecture of Meyniel, Murky graphs, A semi-strong perfect graph theorem, A new property of critical imperfect graphs and some consequences, Locally perfect graphs, No antitwins in minimal imperfect graphs, Two classes of perfect graphs, The strong perfect graph conjecture for pan-free graphs, Wings and perfect graphs, All minimal prime extensions of hereditary classes of graphs, Star-cutsets and perfect graphs, Rainbow generalizations of Ramsey theory: A survey, Some properties of minimal imperfect graphs, Optimal guard sets and the Helly property, Graphical properties related to minimal imperfection, Zur Theorie der perfekten Graphen, On CIS circulants, On a graph of monogenic semigroups, Substitution-closed pattern classes, Entropy of symmetric graphs, Well-covered circulant graphs, On the behavior of the \(N_{+}\)-operator under blocker duality, Discrete extremal problems, Complexity of independent set reconfigurability problems, A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs, A classification of certain graphs with minimal imperfection properties, On the closure of triangle-free graphs under substitution, On the combinatorial problems which I would most like to see solved, On the strong perfect graph conjecture and critical graphs, The ellipsoid method and its consequences in combinatorial optimization, Substitution and \(\chi\)-boundedness, On stable set polyhedra for K//(1,3)free graphs, Maximum degree and fractional matchings in uniform hypergraphs, How to guard a graph?, Fair cost allocations under conflicts - a game-theoretic point of view -, Rees algebras and polyhedral cones of ideals of vertex covers of perfect graphs, The complexity of recognizing linear systems with certain integrality properties, Coloring perfect graphs with no balanced skew-partitions, Hadwiger's conjecture for inflations of 3-chromatic graphs, An algorithm for finding homogeneous pairs, Strongly balanced cooperative games, Perfect zero-divisor graphs, Perfect couples of graphs, Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets, Coflow polyhedra, Preperfect graphs, Excluding paths and antipaths, On generalized perfect graphs: Bounded degree and bounded edge perfection, On slim graphs, even pairs, and star-cutsets, Bounded vertex colorings of graphs, Lehman's forbidden minor characterization of ideal 0-1 matrices, The Erdős-Hajnal conjecture for bull-free graphs, The convex hull of antichains in posets, Not complementary connected and not CIS \(d\)-graphs form weakly monotone families, Decomposing complete edge-chromatic graphs and hypergraphs. Revisited, A note on kernels and Sperner's Lemma, A polyhedral approach to the stability of a family of coalitions, A magnetic procedure for the stability number, The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs, Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree, Some inequalities on the chromatic number of a graph, Some remarks on Hajós' conjecture, A class of facet producing graphs for vertex packing polyhedra, On the ratio of optimal integral and fractional covers, Some partitions associated with a partially ordered set, On formal fractions associated with the symmetric groups, Cyclic orders, Approximability of clique transversal in perfect graphs, Constructions for normal graphs and some consequences, Duality for semiantichains and unichain coverings in products of special posets, Game-perfect graphs, A note on finding all homogeneous set sandwiches, Two-colorable graph states with maximal Schmidt measure, A min-max relation for the partial q-colourings of a graph. II: Box perfection, Independence polynomials of circulants with an application to music, Triangle-free strongly circular-perfect graphs, A notion of cross-perfect bipartite graphs, Mind the independence gap, Vertex- and edge-minimal and locally minimal graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, On a geometric property of perfect graphs, Perfectness and Dilworth number, Tolerance graphs, Decomposition of perfect graphs, Some sequences associated with combinatorial structures, Unavoidable induced subgraphs in large graphs with no homogeneous sets, An integer analogue of Carathéodory's theorem, On the independence polynomial of the corona of graphs, On algorithms for (\(P_5\), gem)-free graphs, The graph sandwich problem for 1-join composition is NP-complete, Near-perfect matrices, New classes of Berge perfect graphs, The facets and the symmetries of the approval-voting polytope, Different capacities of a digraph, Perfect graphs with no \(P_ 5\) and no \(K_ 5\), On dart-free perfectly contractile graphs, Lift-and-project ranks and antiblocker duality, Complexity of list coloring problems with a fixed total number of colors, Generalized perfect graphs: Characterizations and inversion, Recognizing bull-free perfect graphs, On a class of square-free graphs, Motivations and history of some of my conjectures, On perfect \(0,\pm 1\) matrices, Path parity and perfection, Perfect graphs with unique \(P_ 4\)-structure, Subgroup sum graphs of finite abelian groups, Combinatorial differential algebra of \(x^p\), Fractional and integral colourings, On edge perfectness and classes of bipartite graphs, Hall's and Kőnig's theorem in graphs and hypergraphs, Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions, Optimal channel allocation for several types of cellular radio networks, Chair-free Berge graphs are perfect, On a conjecture about uniquely colorable perfect graphs, On essential components and critical sets of a graph, On the closure of graphs under substitution, Balanced \(0,\pm 1\)-matrices, bicoloring and total dual integrality, Applying Lehman's theorems to packing problems, On the connectivity and independence number of power graphs of groups, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Minimal imperfect graphs: A simple approach, On box-perfect graphs, On some graph classes related to perfect graphs: a survey, Packing boxes with harmonic bricks, On certain polytopes associated with graphs, Game-perfect digraphs, Unconditional reflexive polytopes, A class of perfect graphs containing \(P_{6}\), Partially concurrent open shop scheduling with integral preemptions, Graphs vertex-partitionable into strong cliques, Graph covers using \(t\)-colourable vertex sets., On circular-perfect graphs: a survey, Stable effectivity functions and perfect graphs, Forced color classes, intersection graphs and the strong perfect graph conjecture, Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs, Erdős-Hajnal for cap-free graphs, Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture, On the mixed set covering, packing and partitioning polytope, Fractional solutions for capacitated NTU-games, with applications to stable matchings, Perfect graphs and guarding rectilinear art galleries, Hadwiger's conjecture and inflations of the Petersen graph, \(\mathcal Q\)-Ramsey classes of graphs, A combinatorial approach to nonlocality and contextuality, Small 1-defective Ramsey numbers in perfect graphs, Perfect \(f\)-matchings and \(f\)-factors in hypergraphs -- a combinatorial approach, The \(k\)-dominating graph, Basic perfect graphs and their extensions, Almost integral polyhedra related to certain combinatorial optimization problems, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Matroidal graphs, Classification de certaines matrices 0-1, Critical perfect graphs and perfect 3-chromatic graphs, The matroids with the max-flow min-cut property, Infinite triangulated graphs, Some indices over a new algebraic graph, Line graphs of monogenic semigroup graphs, Trivially perfect graphs, On the perfect graph conjecture, Forbidden subgraphs of power graphs, Perfectness of clustered graphs, Combinatorial designs related to the strong perfect graph conjecture, Solution of two fractional packing problems of Lovász, Induced matchings, On the \(P_ 4\)-structure of perfect graphs. IV: Partner graphs, Matchings and covers in hypergraphs, Optimisation and hypergraph theory, A note on the semi-strong perfect graph conjecture, Probabilistic refinement of the asymptotic spectrum of graphs, Recolouring weakly chordal graphs and the complement of triangle-free graphs, Stable families of coalitions and normal hypergraphs, Odd cycles and matrices with integrality properties, Minimax relations for the partial q-colorings of a graph, Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture, Uniquely colorable perfect graphs, On the odd cycles of normal graphs, On the disc-structure of perfect graphs. I: The co-paw-structure, Edge-disjoint odd cycles in graphs with small chromatic numbers, Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers, Edge-choosability in line-perfect multigraphs, Enumerative aspects of certain subclasses of perfect graphs, Graph imperfection. I, Graph imperfection. II, On the properties of weighted minimum colouring games, Normal fraternally orientable graphs satisfy the strong perfect graph conjecture, Quasi-star-cutsets and some consequences, On the Laplacian spectrum of (\(\alpha,\omega\))-graphs, \(\alpha\)-diperfect digraphs, An efficient algorithm for solving the homogeneous set sandwich problem, Point partition numbers: perfect graphs, Problems close to my heart, On chromatic number and perfectness of fuzzy graph, Perfectness of \(G\)-generalized join of graphs, Spectral theory of weighted hypergraphs via tensors, Disjointness graphs of segments in the space, Geometric inequalities for anti-blocking bodies, Integer round-up property for the chromatic number of some \(h\)-perfect graphs, Comparing Imperfection Ratio and Imperfection Index for Graph Classes, The story of perfectly orderable graphs, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Eternal domination and clique covering, On box totally dual integral polyhedra, Reconfiguration of colorable sets in classes of perfect graphs, Testing superperfection of k-trees, On fully orientability of 2-degenerate graphs, Some properties on the lexicographic product of graphs obtained by monogenic semigroups, Excluding Induced Subdivisions of the Bull and Related Graphs, The A4-structure of a graph, Testing Consumer Rationality Using Perfect Graphs and Oriented Discs, Two-colourings that decompose perfect graphs, An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem, Unnamed Item, On a Class of P 5 -Free Graphs, Perfect graphs for domination games, Characterizations of \((4 K_1,C_4,C_5)\)-free graphs, On perfect graphs and polyhedra with (0, 1)-valued extreme points, The Hadwiger number, chordal graphs and \(ab\)-perfection, Counting List Matrix Partitions of Graphs, Covering, Packing and Generalized Perfection, Complementation in T-perfect graphs, A Class of Balanced Matrices Arising from Location Problems, Two Double Poset Polytopes, Review of the theory of stable matchings and contract systems, A mickey-mouse decomposition theorem, Coloring rings, Domination in digraphs and their direct and Cartesian products, Attempting perfect hypergraphs, A Sum of Squares Characterization of Perfect Graphs, On the dot product of graphs over monogenic semigroups, Amalgams and χ-Boundedness, Bounding clique-width via perfect graphs, Alternatives for testing total dual integrality, Perfect graphs, kernels, and cores of cooperative games, Balanced matrices, Matrix partitions of perfect graphs, ON THE COMPLEMENT OF THE ZERO-DIVISOR GRAPH OF A PARTIALLY ORDERED SET, Perfect non-commuting graphs of matrices over chains, Reconfiguration of cliques in a graph, Sorting under partial information (without the ellipsoid algorithm)., ARITHMETIC ASPECTS OF SYMMETRIC EDGE POLYTOPES, 2-clique-bond of stable set polyhedra, The maximum vertex coverage problem on bipartite graphs, Random perfect graphs, Edge-colouring of regular graphs of large degree, On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs, Combinatorial symbolic powers, 2-Matchings and 2-covers of hypergraphs, Gallai colorings and domination in multipartite digraphs, Graphs defined on groups, Skew partitions in perfect graphs, On the strong perfect graph conjecture, Exploring the relationship between max-cut and stable set relaxations, Compositions for perfect graphs, Perfect, ideal and balanced matrices, Line perfect graphs, Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint), Solution of two fractional packing problems of Lovász. (Reprint), The perfection and recognition of bull-reducible Berge graphs, On the sibling-structure of perfect graphs, On minimal forbidden subgraph characterizations of balanced graphs, On line perfect graphs, A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant, Norms and perfect graphs, Clique-perfectness of complements of line graphs, The intersection of two vertex coloring problems, SOME PROPERTIES ON THE DISJUNCTIVE PRODUCT OVER GRAPHS OF MONOGENIC SEMIGROUPS, On minimal forbidden subgraph characterizations of balanced graphs, Implosive graphs: Square-free monomials on symbolic Rees algebras, On the linear extension complexity of stable set polytopes for perfect graphs, Detecting strong cliques, PERFECTION IN R-PROCESSES, A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS, OPEN PACKING NUMBER FOR SOME CLASSES OF PERFECT GRAPHS, Unnamed Item, On Vertices and Facets of Combinatorial 2-Level Polytopes, Une classe d'hypergraphes bichromatiques, Edge colorings of complete graphs without tricolored triangles, Edmonds polytopes and a hierarchy of combinatorial problems, Skew partition sandwich problem is NP-complete, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Structure of cubic Lehman matrices, Finite checkability for integer rounding properties in combinatorial programming problems, Integer Rounding for Polymatroid and Branching Optimization Problems, Perfect Digraphs, A new characterization of trivially perfect graphs, Polynomial algorithms for a class of linear programs, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, Recent developments on the power graph of finite groups – a survey, Suppression distance computation for hierarchical clusterings, On maximum independent set of categorical product and ultimate categorical ratios of graphs, Properties of vertex packing and independence system polyhedra, Perfect zero–one matrices, Convex-round graphs are circular-perfect
Cites Work
