Transformations which Preserve Perfectness and H-Perfectness of Graphs

DOI10.1016/S0304-0208(08)72445-9MaRDI QIDQ3967551zbMATH OpenOpenAlexFDO

Authors Jean Fonlupt, Jean-Pierre Uhry

Publication date 1982

Published in North-Holland Mathematics Studies (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-0208(08)72445-9

zbMATH Keywords

bipartite graphchromatic numberclique numberh-perfect graphsperfect graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cited in

(41)

• Coloring Artemis graphs
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• Decomposition of perfect graphs
• Relaxations of vertex packing
• Matrices with the Edmonds-Johnson property
• A new property of critical imperfect graphs and some consequences
• Locally perfect graphs
• On cutting-plane proofs in combinatorial optimization
• Even pairs in claw-free perfect graphs
• Short-chorded and perfect graphs
• On minimal imperfect graphs without induced P₅
• Quasi-parity and perfect graphs
• Path parity and perfection
• On planar perfectly contractile graphs
• About skew partitions in minimal imperfect graphs
• A transformation which preserves the clique number
• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• On dart-free perfectly contractile graphs
• Integer round-up property for the chromatic number of some \(h\)-perfect graphs
• Finding induced paths of given parity in claw-free graphs
• A class of perfectly contractile graphs
• Complementation in T-perfect graphs
• Claw-free t-perfect graphs can be recognized in polynomial time
• Characterising claw-free t-perfect graphs
• \(K_{4}\)-free graphs with no odd hole: even pairs and the circular chromatic number
• Coloring Meyniel graphs in linear time
• On claw-free t-perfect graphs
• \(t\)-perfection in \(P_5\)-free graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
• Graph transformations preserving the stability number
• Graph transformations preserving the stability number
• Stability preserving transformations of graphs
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• On the structure of bull-free perfect graphs
• Counterexamples to three conjectures concerning perfect graphs
• Contractions in perfect graphs
• Even pairs in Berge graphs with no balanced skew-partitions
• Improved algorithms for perfect graphs and odd holes
• A class of h-perfect graphs
• A magnetic procedure for the stability number

This page was built for publication: Transformations which Preserve Perfectness and H-Perfectness of Graphs

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