On diameters and radii of bridged graphs
From MaRDI portal
Publication:1117245
DOI10.1016/0012-365X(89)90268-9zbMath0667.05036MaRDI QIDQ1117245
Publication date: 1989
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items (52)
Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Blocker size via matching minors ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Radius versus diameter in cocomparability and intersection graphs ⋮ Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ Tent and a subclass of \(P_{5}\)-free graphs ⋮ Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs ⋮ Vertex coloring of graphs with few obstructions ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Structural parameterizations with modulator oblivion ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Triangulated neighborhoods in even-hole-free graphs ⋮ From matchings to independent sets ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Solving the clique cover problem on (bull, \(C_4\))-free graphs ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ A Generalization of $$\chi $$-Binding Functions ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Unnamed Item ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ Some results on maximum stable sets in certain \(P_{5}\)-free graphs ⋮ Unnamed Item ⋮ Coloring square-free Berge graphs ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ On graphs without a \(C_{4}\) or a diamond ⋮ On Toughness and Hamiltonicity of 2K2‐Free Graphs ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Parameterized complexity of conflict-free set cover ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ Wait-free approximate agreement on graphs ⋮ Wait-free approximate agreement on graphs ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences ⋮ Combinatorial optimization with 2-joins ⋮ Consequences of an algorithm for bridged graphs ⋮ Dismantlability of weakly systolic complexes and applications ⋮ On efficient domination for some classes of \(H\)-free bipartite graphs ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs
Cites Work
- On rigid circuit graphs
- On powers and centers of chordal graphs
- On local convexity in graphs
- On the null-homotopy of bridged graphs
- Bridged graphs and geodesic convexity
- On bridged graphs and cop-win graphs
- Conditions for invariance of set diameters under d-convexification in a graph
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- Convexity in Graphs and Hypergraphs
This page was built for publication: On diameters and radii of bridged graphs
