The Complexity of the List Partition Problem for Graphs
From MaRDI portal
Publication:3544241
DOI10.1137/060666238zbMath1151.05045OpenAlexW1967387782MaRDI QIDQ3544241
Elaine M. Eschen, R. Sritharan, Kathie Cameron, Chính T. Hoàng
Publication date: 5 December 2008
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://researchrepository.wvu.edu/faculty_publications/364
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (16)
Algorithms to approximately count and sample conforming colorings of graphs ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Obstructions to partitions of chordal graphs ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ Clique versus independent set ⋮ The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ The monotonicity property of \(M\)-partition problems ⋮ The external constraint 4 nonempty part sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ \(2K_{2}\) vertex-set partition into nonempty parts ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ Graph partitions with prescribed patterns
This page was built for publication: The Complexity of the List Partition Problem for Graphs
