Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs

DOI10.1016/S0166-218X(99)00149-3MaRDI QIDQ1962062zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan

Publication date 10 May 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00149-3

zbMATH Keywords

maximum cliquegreedy algorithmoptimization algorithmrecognition algorithmminimum coloringchordal bipartitestrongly chordalelimination orderingstrongly orderable graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75)

Recommendations

• scientific article; zbMATH DE number 1302027
• scientific article; zbMATH DE number 2086689
• Properly orderable graphs
• A characterization of strongly chordal graphs
• New classes of perfectly orderable graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 1107732 (Why is no real title available?)
• A characterization of perfect graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Domination, independent domination, and duality in strongly chordal graphs
• Doubly Lexical Orderings of Matrices
• Doubly lexical ordering of dense 0--1 matrices
• Greedoids
• Labeling algorithms for domination problems in sun-free chordal graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Steiner trees, connected domination and strongly chordal graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Three Partition Refinement Algorithms
• Weakly triangulated graphs

Cited in

(13)

• Computing a minimum paired-dominating set in strongly orderable graphs
• Finding a sun in building-free graphs
• Strong Chordality of Graphs with Possible Loops
• \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs
• scientific article; zbMATH DE number 2086689 (Why is no real title available?)
• Coloring squares of graphs via vertex orderings
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• The Perfect Matching Reconfiguration Problem
• Perfect circular arc coloring
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• Edge erasures and chordal graphs
• Gallai-like characterization of strong cocomparability graphs
• The graphs that Dahlhaus called ``good generalized strongly chordal

This page was built for publication: Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs

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