A note on the computational complexity of graph vertex partition

DOI10.1016/j.dam.2006.06.003zbMath1108.68063OpenAlexW2058728300MaRDI QIDQ868398

Yu-Ming Chu, Yuan Qiu Huang

Publication date: 2 March 2007

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

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

zbMATH Keywords

stable setpolynomial algorithmgraph partitiondeficiency numberXuong tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (2)

On equistable, split, CIS, and related classes of graphs ⋮ Stable-\(\Pi\) partitions of graphs

Cites Work

• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases
• How to determine the maximum genus of a graph
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Clique and anticlique partitions of graphs
• Partitions of graphs into one or two independent sets and cliques
• Graph Ear Decompositions and Graph Embeddings

This page was built for publication: A note on the computational complexity of graph vertex partition