Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
From MaRDI portal
Publication:1883661
zbMath1053.05046arXivmath/0306158MaRDI QIDQ1883661
Publication date: 13 October 2004
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0306158
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Trees, paths, stars, caterpillars and spiders ⋮ Harary polynomials ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ On invariants of hereditary graph properties ⋮ Monopolar graphs: complexity of computing classical graph parameters ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Minimal obstructions to 2-polar cographs ⋮ Minimal obstructions to \(( s , 1 )\)-polarity in cographs ⋮ Inductive graph invariants and approximation algorithms ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ Some problems on induced subgraphs ⋮ Unnamed Item ⋮ List monopolar partitions of claw-free graphs ⋮ Complexity and algorithms for recognizing polar and monopolar graphs ⋮ Generalized Coloring of Permutations ⋮ On the complexity of generalized chromatic polynomials ⋮ The complexity of partitioning into disjoint cliques and a triangle-free graph ⋮ Polarity of chordal graphs ⋮ Minimization and parameterized variants of vertex partition problems on graphs ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ On the Polarity and Monopolarity of Graphs ⋮ Minimal obstructions to \(( \infty , k )\)-polarity in cographs ⋮ On \(P_4\)-transversals of chordal graphs ⋮ Unique Factorization Theorem and Formal Concept Analysis ⋮ Algorithms for unipolar and generalized split graphs ⋮ Solving partition problems with colour-bipartitions ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ Partitioning a graph into disjoint cliques and a triangle-free graph
