The complexity of partitioning into disjoint cliques and a triangle-free graph

DOI10.1016/j.dam.2016.10.004zbMath1358.05226arXiv1512.02207OpenAlexW2963676992MaRDI QIDQ516874

Marin Bougeret, Pascal Ochem

Publication date: 15 March 2017

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

Full work available at URL: https://arxiv.org/abs/1512.02207

zbMATH Keywords

graph coloringNP-completeness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Unnamed Item ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Cites Work

• Unnamed Item
• Unnamed Item
• The structure of bull-free graphs II and III -- a summary
• Paw-free graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Colorings and girth of oriented planar graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Dynamic cage survey