Degree-constrained 2-partitions of graphs

DOI10.1016/j.tcs.2018.12.023zbMath1427.68226arXiv1801.06216OpenAlexW2963251415MaRDI QIDQ2419120

Jörgen Bang-Jensen, Stéphane Bessy

Publication date: 29 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

minimum degreepolynomial time2-partition\(\mathcal{NP}\)-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (1)

On the computational complexity of the bipartizing matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding good 2-partitions of digraphs. I. Hereditary properties
• FPT algorithms for connected feedback vertex set
• Complexity and kernels for bipartition into degree-bounded induced graphs
• Partition of graphs with condition on the connectivity and minimum degree
• Efficient algorithms for decomposing graphs under degree constraints
• A linear algorithm for bipartition of biconnected graphs
• Partitioning graphs into connected parts
• On the complexity of partitioning graphs into connected subgraphs
• Partitions of graphs with high minimum degree or connectivity.
• Splitting a graph into disjoint induced paths or cycles.
• Algorithmic approach to the satisfactory graph partitioning problem
• Independent feedback vertex sets for graphs of bounded diameter
• On the complexity of partitioning a graph into a few connected subgraphs
• On partitions of graphs under degree constraints
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• The satisfactory partition problem
• Bipartition of graph under degree constraints
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Defective coloring revisited
• Recognizing decomposable graphs
• Splitting digraphs
• Graph decomposition with constraints on the connectivity and minimum degree
• On decomposition of triangle-free graphs under degree constraints
• Recognizing Graphs Close to Bipartite Graphs
• Digraphs
• Connected Feedback Vertex Set in Planar Graphs

This page was built for publication: Degree-constrained 2-partitions of graphs