The Complexity of the List Partition Problem for Graphs
DOI10.1137/060666238zbMATH Open1151.05045OpenAlexW1967387782MaRDI QIDQ3544241FDOQ3544241
Authors: Kathie Cameron, Elaine M. Eschen, R. Sritharan, 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (31)
- Two algorithms for general list matrix partitions
- Graph partitions with prescribed patterns
- Graph partitions: recent progresses and some open problems
- Clique versus independent set
- The complexity of surjective homomorphism problems-a survey
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- The monotonicity property of \(M\)-partition problems
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- Algorithms to approximately count and sample conforming colorings of graphs
- Partitioning a graph into disjoint cliques and a triangle-free graph
- An efficiently solvable graph partition problem to which many problems are reducible
- List monopolar partitions of claw-free graphs
- Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
- The external constraint 4 nonempty part sandwich problem
- Solving partition problems almost always requires pushing many vertices around
- \(2K_2\)-partition of some classes of graphs
- \(2K_{2}\) vertex-set partition into nonempty parts
- Dichotomy for tree-structured trigraph list homomorphism problems
- 2K2-Partition Problem
- Parameterizing cut sets in a graph by the number of their components
- The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
- The parameterised complexity of list problems on graphs of bounded treewidth
- The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem
- NP-hard and linear variants of hypergraph partitioning
- Digraph matrix partitions and trigraph homomorphisms
- 2K2 vertex-set partition into nonempty parts
- The list partition problem for graphs
- A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more)
- Obstructions to partitions of chordal graphs
- Complexity of graph partition problems
- Minimal disconnected cuts in planar graphs
This page was built for publication: The Complexity of the List Partition Problem for Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3544241)
