Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

DOI10.1016/j.jcss.2017.08.002zbMath1380.68227arXiv1702.04322OpenAlexW2963464338MaRDI QIDQ1678166

Christian Komusiewicz, Erik Jan van Leeuwen, Manuel Sorge, Iyad A. Kanj

Publication date: 14 November 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

split graphsfixed-parameter algorithmsgraph classesmonopolar graphsunipolar graphssubcoloringsvertex-partition problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Monopolar graphs: complexity of computing classical graph parameters ⋮ Unnamed Item ⋮ Minimization and parameterized variants of vertex partition problems on graphs ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• More about subcolorings
• List monopolar partitions of claw-free graphs
• Finding odd cycle transversals.
• Algorithms for unipolar and generalized split graphs
• Solving partition problems with colour-bipartitions
• Polarity of chordal graphs
• The splittance of a graph
• The complexity of some problems related to GRAPH 3-COLORABILITY
• The complexity of \(G\)-free colourability
• Subcolorings and the subchromatic number of a graph
• Which problems have strongly exponential complexity?
• Recognition of unipolar and generalised split graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Complexity and algorithms for recognizing polar and monopolar graphs
• Wheel-Free Deletion Is W[2-Hard]
• On the computational complexity of (O,P)-partition problems
• Graph Subcolorings: Complexity and Algorithms
• On the Polarity and Monopolarity of Graphs
• On 2-Subcolourings of Chordal Graphs
• Parameterized Algorithms
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis