Independent sets in \((P_4+P_4\),triangle)-free graphs

DOI10.1007/s00373-021-02340-7zbMath1479.05282arXiv2003.08649OpenAlexW3166205065MaRDI QIDQ2053685

Raffaele Mosca

Publication date: 30 November 2021

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.08649

zbMATH Keywords

polynomial algorithmstriangle-free graphsmaximum independent set problem\(S_{i, j, k}\)-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• On the closure of triangle-free graphs under substitution
• Paw-free graphs
• On diameters and radii of bridged graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Computing independent sets in graphs with large girth
• Geometric algorithms and combinatorial optimization
• Some simplified NP-complete graph problems
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• A note on triangle-free and bipartite graphs
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
• From matchings to independent sets
• A Linear Recognition Algorithm for Cographs
• A New Algorithm for Generating All the Maximal Independent Sets
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Graph Classes: A Survey
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• An upper bound on the number of cliques in a graph
• Independent Set in P₅-Free Graphs in Polynomial Time
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Independent sets in \((P_4+P_4\),triangle)-free graphs