Recognition of unipolar and generalised split graphs (Q1736638)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Recognition of unipolar and generalised split graphs |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Recognition of unipolar and generalised split graphs |
scientific article |
Statements
Recognition of unipolar and generalised split graphs (English)
0 references
26 March 2019
0 references
Summary: 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 an \(O(n^2)\)-time algorithm for recognition of \(n\)-vertex generalised split graphs, improving on previous \(O(n^3)\)-time algorithms.
0 references
unipolar graphs
0 references
generalised split graphs
0 references
perfect graphs
0 references
recognition algorithms
0 references
representations
0 references
