Recognition of unipolar and generalised split graphs

DOI10.3390/A8010046zbMATH Open1461.05216arXiv1604.00922OpenAlexW1973229660MaRDI QIDQ1736638FDOQ1736638

Nikola Yolov, Colin McDiarmid

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Title not available (Why is that?)
• Recognizing Berge graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Almost all Berge Graphs are Perfect
• Title not available (Why is that?)
• Algorithms for unipolar and generalized split graphs
• Solving partition problems with colour-bipartitions

Cited In (8)

• Recognizing Graphs Close to Bipartite Graphs
• Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
• Recognition of overlap graphs
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Random perfect graphs
• Vertex splitting and the recognition of trapezoid graphs
• Weighted Efficient Domination for $P_5$-Free and $P_6$-Free 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)