Weakly triangulated graphs
From MaRDI portal
Publication:801088
DOI10.1016/0095-8956(85)90050-4zbMath0551.05055OpenAlexW2082068582WikidataQ56656644 ScholiaQ56656644MaRDI QIDQ801088
Publication date: 1985
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(85)90050-4
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)
Related Items (only showing first 100 items - show all)
Some results on connected vertex separators ⋮ Vertex cut of a graph and connectivity of its neighbourhood complex ⋮ Generating weakly chordal graphs from arbitrary graphs ⋮ Chordal graphs and their clique graphs ⋮ On 3-degree 4-chordal graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ On domination elimination orderings and domination graphs ⋮ Independent domination in hereditary classes ⋮ NeST graphs ⋮ A generalization of chordal graphs and the maximum clique problem ⋮ Slightly triangulated graphs are perfect ⋮ Alternating orientation and alternating colouration of perfect graphs ⋮ Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday) ⋮ Unnamed Item ⋮ Algorithms for weakly triangulated graphs ⋮ Mock threshold graphs ⋮ Characterizing and recognizing the visibility graph of a funnel-shaped polygon ⋮ Recognizing bull-free perfect graphs ⋮ A Characterization of b-Perfect Graphs ⋮ On domination problems for permutation and other graphs ⋮ Murky graphs ⋮ \(r\)-dominating cliques in graphs with hypertree structure ⋮ Path parity and perfection ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ Perfect graphs with unique \(P_ 4\)-structure ⋮ Discs in unbreakable graphs ⋮ Powers of distance-hereditary graphs ⋮ A new property of critical imperfect graphs and some consequences ⋮ Locally perfect graphs ⋮ Chordal multipartite graphs and chordal colorings ⋮ Symmetric graph-theoretic roles of two-pairs and chords of cycles ⋮ On a conjecture of Hoàng and Tu concerning perfectly orderable graphs ⋮ Novel evolutionary models and applications to sequence alignment problems ⋮ Almost all Berge Graphs are Perfect ⋮ On edge perfectness and classes of bipartite graphs ⋮ Treewidth for graphs with small chordality ⋮ A characterization of interval catch digraphs ⋮ Opposition graphs are strict quasi-parity graphs ⋮ Recognizing claw-free perfect graphs ⋮ On the complexity of recognizing a class of perfectly orderable graphs ⋮ Recognizing interval digraphs and interval bigraphs in polynomial time ⋮ Meyniel weakly triangulated graphs. II: A theorem of Dirac ⋮ On the perfect orderability of unions of two graphs ⋮ Skew rank decompositions ⋮ A note on \(r\)-dominating cliques ⋮ New graph classes characterized by weak vertex separators and two-pairs ⋮ On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs ⋮ A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree ⋮ Homogeneously orderable graphs ⋮ Some problems on induced subgraphs ⋮ Characterisations and Linear-Time Recognition of Probe Cographs ⋮ The multiple domination and limited packing problems in graphs ⋮ Classes of perfect graphs ⋮ Graphs vertex-partitionable into strong cliques ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Covering orthogonal polygons with star polygons: The perfect graph approach ⋮ Recognition and isomorphism of tree-like \(P_4\)-connected graphs ⋮ Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs ⋮ On simplicial and co-simplicial vertices in graphs. ⋮ Dominating sets in perfect graphs ⋮ Short-chorded and perfect graphs ⋮ An analogue of Hajós’ Theorem for the circular chromatic number ⋮ Finding large holes ⋮ Sum-perfect graphs ⋮ Polar SAT and related graphs ⋮ On the structure of bull-free perfect graphs ⋮ Meyniel weakly triangulated graphs. I: Co-perfect orderability ⋮ A charming class of perfectly orderable graphs ⋮ The critical node detection problem in networks: a survey ⋮ A characterization of 2-tree proper interval 3-graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Transitive orientations in bull-reducible Berge graphs ⋮ On Roussel-Rubio-type lemmas and their consequences ⋮ Skew partitions in perfect graphs ⋮ A magnetic procedure for the stability number ⋮ Domination graphs: Examples and counterexamples ⋮ Disjoint clique cutsets in graphs without long holes ⋮ POINT VISIBILITY GRAPHS AND ${\mathcal O}$-CONVEX COVER ⋮ The complexity of dissociation set problems in graphs ⋮ Interval \(k\)-graphs and orders ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ Neighborhood subtree tolerance graphs ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ On the \(P_ 4\)-structure of perfect graphs. IV: Partner graphs ⋮ Coloring Artemis graphs ⋮ A generalization of Chvátal's star-cutset lemma ⋮ Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)] ⋮ Maximum weight independent sets in hole- and co-chair-free graphs ⋮ Optimizing weakly triangulated graphs ⋮ Combinatorial optimization with 2-joins ⋮ On probe interval graphs ⋮ Extension and its price for the connected vertex cover problem ⋮ A simple nc algorithm to recognize weakly triangulated graphs ⋮ Bichromatic \(P_{4}\)-composition schemes for perfect orderability ⋮ On the disc-structure of perfect graphs. I: The co-paw-structure ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ Tree-like \(P_4\)-connected graphs ⋮ A separator-based method for generating weakly chordal graphs ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
Cites Work
This page was built for publication: Weakly triangulated graphs
