Graphical properties related to minimal imperfection

DOI10.1016/0012-365X(79)90065-7zbMATH Open0421.05028MaRDI QIDQ1132889FDOQ1132889

Authors: S. H. Smith 

Publication date: 1979

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

minimal imperfect graphspartitionable graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Normal hypergraphs and the perfect graph conjecture
• A class of facet producing graphs for vertex packing polyhedra
• On certain polytopes associated with graphs
• A characterization of perfect graphs
• Title not available (Why is that?)
• Blocking and anti-blocking pairs of polyhedra
• Almost integral polyhedra related to certain combinatorial optimization problems
• Perfect zero–one matrices
• Coloring a Family of Circular Arcs
• Critical perfect graphs and perfect 3-chromatic graphs
• On the perfect graph conjecture
• Line perfect graphs
• Anti-blocking polyhedra
• Title not available (Why is that?)
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• The Strong Perfect Graph Conjecture for Planar Graphs
• On the strong perfect graph conjecture
• Title not available (Why is that?)
• The history of the perfect graphs

Cited In (34)

• Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture
• Structure of cubic Lehman matrices
• An approach to solving \(A^{k}=J-I\)
• Some colouring problems for Paley graphs
• Near-perfect matrices
• Cayley partitionable graphs and near-factorizations of finite groups
• Two classes of perfect graphs
• Generalized perfect graphs: Characterizations and inversion
• A Sum of Squares Characterization of Perfect Graphs
• A note on even pairs
• On classes of minimal circular-imperfect graphs
• On minimal imperfect graphs without induced \(P_5\)
• Grinstead's conjecture is true for graphs with a small clique number
• A construction for non-rank facets of stable set polytopes of webs
• A classification of certain graphs with minimal imperfection properties
• On stable set polyhedra for K//(1,3)free graphs
• Vertex- and edge-minimal and locally minimal graphs
• Comparing imperfection ratio and imperfection index for graph classes
• A note on clutter partitions
• Applying Lehman's theorems to packing problems
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• A vertex critical graph without critical edges
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• On the Laplacian spectrum of (\(\alpha,\omega\))-graphs
• On transversals in minimal imperfect graphs
• Star-cutsets and perfect graphs
• Some properties of minimal imperfect graphs
• On determining the imperfection ratio
• Minimal imperfect graphs: A simple approach
• On perfect graphs and polyhedra with (0, 1)-valued extreme points
• Antitwins in partitionable graphs
• On essential components and critical sets of a graph
• Forced color classes, intersection graphs and the strong perfect graph conjecture
• Completeness for intersection classes

This page was built for publication: Graphical properties related to minimal imperfection

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