Recognition of unipolar and generalised split graphs

DOI10.3390/A8010046MaRDI QIDQ1736638zbMATH OpenOpenAlexFDO

Authors Nikola Yolov, Colin McDiarmid

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

representationsperfect graphsrecognition algorithmsunipolar graphsgeneralised split graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar partition of a graph can be used to find efficiently the clique number, the stability number, the chromatic number, and to solve other problems that are hard for general graphs. We present the first $O(n^2)$ time algorithm for recognition of $n$-vertex unipolar and generalised split graphs, improving on previous $O(n^3)$ time algorithms.

Recommendations

• Algorithms for unipolar and generalized split graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Uniquely monopolar-partitionable block graphs
• Solving partition problems with colour-bipartitions
• Polar cographs

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3977053 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Algorithms for unipolar and generalized split graphs
• Almost all Berge Graphs are Perfect
• On the Complexity of Timetable and Multicommodity Flow Problems
• Recognizing Berge graphs
• Solving partition problems with colour-bipartitions

Cited in

(13)

• Recognizing Graphs Close to Bipartite Graphs
• Recognition of overlap graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Solving partition problems almost always requires pushing many vertices around
• Algorithms for unipolar and generalized split graphs
• Thick forests
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Random perfect graphs
• Weighted efficient domination for P₅-free and P₆-free graphs
• On two variants of split graphs: 2-unipolar graph and k-probe-split graph
• Vertex splitting and the recognition of trapezoid graphs
• Uniquely monopolar-partitionable block graphs

This page was built for publication: Recognition of unipolar and generalised split graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736638)