Independent Sets in Asteroidal Triple-Free Graphs
From MaRDI portal
Publication:4255822
DOI10.1137/S0895480197326346zbMath0918.68072OpenAlexW2154520530MaRDI QIDQ4255822
Haiko Müller, Ton Kloks, Dieter Kratsch, Hajo J. Broersma
Publication date: 27 June 1999
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480197326346
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (32)
On claw-free asteroidal triple-free graphs ⋮ Notes on complexity of packing coloring ⋮ Tent and a subclass of \(P_{5}\)-free graphs ⋮ Hereditary Efficiently Dominatable Graphs ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ 3-colouring AT-free graphs in polynomial time ⋮ Reduced clique graphs of chordal 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 ⋮ Algorithms for graphs with small octopus ⋮ Induced matchings in intersection graphs. ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Feedback vertex set on AT-free graphs ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Separator orders in interval, cocomparability, and AT-free graphs ⋮ On distance-3 matchings and induced matchings ⋮ Improved bottleneck domination algorithms ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ Induced disjoint paths in AT-free graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Mind the independence gap ⋮ Independent packings in structured graphs ⋮ Independent Domination in Triangle Graphs ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results
This page was built for publication: Independent Sets in Asteroidal Triple-Free Graphs
