Maximum weight independent sets in classes related to claw-free graphs

DOI10.1016/j.dam.2015.02.012zbMath1350.05056OpenAlexW2058829003MaRDI QIDQ344862

Frédéric Maffray, T. Karthick

Publication date: 24 November 2016

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

Full work available at URL: https://doi.org/10.1016/j.dam.2015.02.012

zbMATH Keywords

independent setclaw-free graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (10)

Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Parameterized Complexity of Independent Set in H-Free Graphs. ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ Parameterized complexity of independent set in H-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Maximum weight independent sets in hole- and dart-free graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• Finding augmenting chains in extensions of claw-free graphs
• Decomposition by clique separators
• The complexity of generalized clique packing
• On maximal independent sets of vertices in claw-free graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Stability number of bull- and chair-free graphs revisited
• Stable sets in two subclasses of banner-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Recognizing bull-free perfect graphs
• Vertex Disjoint Paths for Dispatching in Railways.
• Data Mining with optimized two-dimensional association rules
• A Linear Recognition Algorithm for Cographs
• On the homogeneous representation of interval graphs
• Graph Classes: A Survey
• Optimizing Bull-Free Perfect Graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Maximum weight independent sets in classes related to claw-free graphs