Quasi-threshold graphs
From MaRDI portal
Publication:1923584
DOI10.1016/0166-218X(96)00094-7zbMath0857.05082MaRDI QIDQ1923584
Jing-Ho Yan, Jer-Jeong Chen, Gerard Jennhwa Chang
Publication date: 26 February 1997
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items (49)
Some new results on generalized additive games ⋮ On the proper orientation number of chordal graphs ⋮ The Micro-world of Cographs ⋮ The micro-world of cographs ⋮ Asymptotic normality of some graph sequences ⋮ On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ Fast Quasi-Threshold Editing ⋮ Mock threshold graphs ⋮ Intersection problem for Droms RAAGs ⋮ On the rank of the distance matrix of graphs ⋮ Hereditary Efficiently Dominatable Graphs ⋮ On graphs with 2 trivial distance ideals ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ Linear optimization over homogeneous matrix cones ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Edge contractions in subclasses of chordal graphs ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Combinatorially interpreting generalized Stirling numbers ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Equistable simplicial, very well-covered, and line graphs ⋮ Integer Laplacian eigenvalues of chordal graphs ⋮ Edge Contractions in Subclasses of Chordal Graphs ⋮ Approximate association via dissociation ⋮ On the chromatic index of join graphs and triangle-free graphs with large maximum degree ⋮ Monotonic stable solutions for minimum coloring games ⋮ The chromatic symmetric functions of trivially perfect graphs and cographs ⋮ Star Partitions of Perfect Graphs ⋮ A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Augmenting graphs for independent sets ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Order consolidation for hierarchical product lines ⋮ The structure and the number of \(P_7\)-free bipartite graphs ⋮ Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem ⋮ A polynomial kernel for trivially perfect editing ⋮ Paired threshold graphs ⋮ Laplacian spectrum of weakly quasi-threshold graphs ⋮ Linear separation of connected dominating sets in graphs ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Probe threshold and probe trivially perfect graphs ⋮ Distance ideals of graphs ⋮ A new characterization of trivially perfect graphs ⋮ Diameter estimates for graph associahedra ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ On the properties of weighted minimum colouring games ⋮ Linear-time recognition of double-threshold graphs ⋮ Defective Coloring on Classes of Perfect Graphs ⋮ Cographs which are cover-incomparability graphs of posets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distance-hereditary graphs
- Complement reducible graphs
- The complexity of comparability graph recognition and coloring
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Trivially perfect graphs
- A Linear Recognition Algorithm for Cographs
- The Comparability Graph of a Tree
- The bandwidth problem for graphs and matrices—a survey
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Note on "The Comparability Graph of a Tree"
This page was built for publication: Quasi-threshold graphs
