Weak bipolarizable graphs

DOI10.1016/0012-365X(89)90208-2MaRDI QIDQ1116961zbMATH OpenFDO

Authors Stephan Olariu

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(89)90208-2

zbMATH Keywords

perfectly orderable graphsrecognition algorithm

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10)

Review text

We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm together with linear-time optimization algorithms for this class of graphs.

Cites work

• A note on superbrittle graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Four classes of perfectly orderable graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• On brittle graphs
• On rigid circuit graphs
• Tolerance graphs
• Topics on perfect graphs

Cited in

(25)

• Some aspects of the semi-perfect elimination
• The maximum clique problem
• Duchet-type theorems for powers of HHD-free graphs
• Finding a central vertex in an HHD-free graph
• Distance labeling scheme and split decomposition
• Recognition of some perfectly orderable graph classes
• Extension of hereditary classes with substitutions
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Convex geometries over induced paths with bounded length
• Quasi-brittle graphs, a new class of perfectly orderable graphs
• Oracles for vertex elimination orderings
• A New Class of Brittle Graphs
• scientific article; zbMATH DE number 4079483 (Why is no real title available?)
• Weakly pancyclic graphs
• Lexbfs-orderings and powers of hhd-free graphs^∗
• Powers of hhd-free graphs^∗
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Computing the hull and interval numbers in the weakly toll convexity
• LexBFS-orderings and powers of graphs
• Characterizations of graph classes via convex geometries: a survey
• Convex geometries yielded by transit functions
• On walk domination: weakly toll domination, l₂ and l₃ domination
• An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
• Bipolarizable graphs
• A fast parallel algorithm to recognize partitionable graphs

This page was built for publication: Weak bipolarizable graphs

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