Asteroidal Triple-Free Graphs
From MaRDI portal
Publication:4377431
DOI10.1137/S0895480193250125zbMath0884.05075OpenAlexW1970088964MaRDI QIDQ4377431
Stephan Olariu, Lorna K. Stewart, Derek Gordon Corneil
Publication date: 9 February 1998
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480193250125
dominating settrapezoid graphscocomparability graphsinterval graphspermutation graphsgraph decompositionsstructural graph theoryasteroidal triplesasteroidal triple-free graphsdominating pairs
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)
Related Items (69)
On claw-free asteroidal triple-free graphs ⋮ Minimal triangulations of graphs: a survey ⋮ Minimal separators in \(P_4\)-sparse graphs ⋮ Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Semitotal domination on AT-free graphs and circle graphs ⋮ Vertex ranking of asteroidal triple-free graphs ⋮ On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs ⋮ Computing a dominating pair in an asteroidal triple-free graph in linear time ⋮ Rainbow connection number and connected dominating sets ⋮ Radius versus diameter in cocomparability and intersection graphs ⋮ Injective hulls of various graph classes ⋮ Graph extremities defined by search algorithms ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ Unnamed Item ⋮ Treewidth for graphs with small chordality ⋮ Triangulating graphs without asteroidal triples ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ Hadwiger Number of Graphs with Small Chordality ⋮ Detecting induced minors in AT-free graphs ⋮ Equivalence between pathbreadth and strong pathbreadth ⋮ Complexity of paired domination in at-free and planar graphs ⋮ New characterizations of proper interval bigraphs ⋮ Rainbow connections of graphs: a survey ⋮ Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem ⋮ Asteroidal triple-free graphs ⋮ Cops and robber on butterflies, grids, and AT-free graphs ⋮ On characterizing proper max-point-tolerance graphs ⋮ Path eccentricity of graphs ⋮ On linear and circular structure of (claw, net)-free graphs ⋮ Connected feedback vertex set on AT-free graphs ⋮ Classes of perfect graphs ⋮ Induced matchings in asteroidal triple-free graphs ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ Hereditary dominating pair graphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Domination and total domination on asteroidal triple-free graphs ⋮ Bandwidth on AT-free graphs ⋮ A note on the geodetic number and the Steiner number of AT-free graphs ⋮ Some properties of edge intersection graphs of single-bend paths on a grid ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Feedback vertex set on AT-free graphs ⋮ Linear time algorithms for dominating pairs in asteroidal triple-free graphs ⋮ Convex and isometric domination of (weak) dominating pair graphs ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ Separator orders in interval, cocomparability, and AT-free graphs ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ Asteroidal triples of moplexes ⋮ Pursuing a fast robber on a graph ⋮ Complexity classification of some edge modification problems ⋮ On the Steiner, geodetic and hull numbers of graphs ⋮ On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs ⋮ Diameter determination on restricted graph families ⋮ Tree-decompositions of small pathwidth ⋮ On forbidden induced subgraphs for unit disk graphs ⋮ Interval \(k\)-graphs and orders ⋮ Efficient algorithms for Roman domination on some classes of graphs ⋮ Induced disjoint paths in AT-free graphs ⋮ On the domination search number ⋮ Localized and compact data-structure for comparability graphs ⋮ Treelike comparability graphs ⋮ Approximability of the Path-Distance-Width for AT-free Graphs ⋮ AT-free graphs: Linear bounds for the oriented diameter ⋮ On stable cutsets in graphs ⋮ Some properties of edge intersection graphs of single bend paths on a grid ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Asteroidal Triple of Edges in Bichordal Graphs: A Complete list ⋮ Asteroidal Chromatic Number of a Graph
This page was built for publication: Asteroidal Triple-Free Graphs
