Optimizing Bull-Free Perfect Graphs

DOI10.1137/S0895480198339237zbMath1071.05038OpenAlexW2017777390MaRDI QIDQ4652633

Frédéric Maffray, Celina M. Herrera de Figueiredo

Publication date: 28 February 2005

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

Full work available at URL: https://doi.org/10.1137/s0895480198339237

zbMATH Keywords

combinatorial optimizationgraph algorithmsanalysis of algorithms and problem complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (10)

The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ 4-coloring \((P_6, \text{bull})\)-free graphs ⋮ Classes of perfect graphs ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Transitive orientations in bull-reducible Berge graphs ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Combinatorial optimization with 2-joins ⋮ The structure of bull-free graphs I -- three-edge-paths with centers and anticenters ⋮ The Structure of Bull-Free Perfect Graphs

This page was built for publication: Optimizing Bull-Free Perfect Graphs