On star partition of split graphs

DOI10.1007/978-3-031-52213-0_15MaRDI QIDQ6547833

Sethu Vijayakumar, D. Divya

Publication date: 31 May 2024

zbMATH Keywords

NP-completenessfixed parameter tractabilitysplit graphspolynomial time algorithmsstar partition

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A simplified NP-complete MAXSAT problem
• Fundamentals of parameterized complexity
• Domination in convex and chordal bipartite graphs
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Clustering to minimize the maximum intercluster distance
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• A linear algorithm for the domination number of a tree
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Optimal packing of induced stars in a graph
• Star partitions on graphs
• Induced star partition of graphs
• The path partition problem and related problems in bipartite graphs
• Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs
• Set Partitioning via Inclusion-Exclusion
• Domination in permutation graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Star Partitions of Perfect Graphs
• On the completeness of a generalized matching problem
• Star covers and star partitions of double-split graphs
• Star covers and star partitions of cographs and butterfly-free graphs

Related Items (2)

Star covers and star partitions of cographs and butterfly-free graphs ⋮ Ramsey-type problems on induced covers and induced partitions toward the Gyárfás-Sumner conjecture

This page was built for publication: On star partition of split graphs

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