Transformations which Preserve Perfectness and H-Perfectness of Graphs

DOI10.1016/S0304-0208(08)72445-9zbMath0502.05023OpenAlexW1575561304MaRDI QIDQ3967551

Jean-Pierre Uhry, Jean Fonlupt

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 numberperfect graphh-perfect graphs

Mathematics Subject Classification ID

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

Related Items (37)

Relaxations of vertex packing ⋮ Integer round-up property for the chromatic number of some \(h\)-perfect graphs ⋮ On dart-free perfectly contractile graphs ⋮ Quasi-parity and perfect graphs ⋮ Matrices with the Edmonds-Johnson property ⋮ Path parity and perfection ⋮ A new property of critical imperfect graphs and some consequences ⋮ On planar perfectly contractile graphs ⋮ Locally perfect graphs ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Even pairs in claw-free perfect graphs ⋮ Complementation in T-perfect graphs ⋮ $t$-Perfection in $P_5$-Free Graphs ⋮ Finding induced paths of given parity in claw-free graphs ⋮ On claw-free \(t\)-perfect graphs ⋮ Stability preserving transformations of graphs ⋮ Short-chorded and perfect graphs ⋮ On the structure of bull-free perfect graphs ⋮ Counterexamples to three conjectures concerning perfect graphs ⋮ Graph transformations preserving the stability number ⋮ A magnetic procedure for the stability number ⋮ A min-max relation for stable sets in graphs with no odd-\(K_ 4\) ⋮ Graph transformations preserving the stability number ⋮ K4-free graphs with no odd hole: Even pairs and the circular chromatic number ⋮ Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time ⋮ Coloring Artemis graphs ⋮ On minimal imperfect graphs without induced \(P_5\) ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ Characterising claw-free t-perfect graphs ⋮ About skew partitions in minimal imperfect graphs ⋮ A transformation which preserves the clique number ⋮ No odd pairs in minimal imperfect NP\({}_{5}\) graphs. ⋮ Unnamed Item ⋮ A class of h-perfect graphs ⋮ A class of perfectly contractile graphs ⋮ Coloring Meyniel graphs in linear time ⋮ Decomposition of perfect graphs

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