The complexity of comparability graph recognition and coloring

Cites work

scientific article; zbMATH DE number 3172312 (Why is no real title available?)
scientific article; zbMATH DE number 3496192 (Why is no real title available?)
scientific article; zbMATH DE number 3400923 (Why is no real title available?)
A Characterization of Comparability Graphs and of Interval Graphs
Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
Comparability graphs and a new matroid
Partially ordered sets and their comparability graphs
Permutation Graphs and Transitive Graphs
Transitiv orientierbare Graphen
Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(48)

Comparability graphs and intersection graphs
Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
On semi-$P_ 4$-sparse graphs
On the edge-integrity of some graphs and their complements
Quasi-threshold graphs
On $H$-topological intersection graphs
On the thinness of trees
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
On the complexity of a family of generalized matching problems
Thinness of product graphs
Distance-$d$ independent set problems for bipartite and chordal graphs
Chronological orderings of interval graphs
Stage-graph representations
Comparability graphs and a new matroid
Characterization of $\mathrm{B}_0$-VPG cocomparability graphs and a 2D visualization of their posets
Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
On finding a minimum vertex cover of a series-parallel graph
Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
The recognition of triangle graphs
Comparability digraphs: an analogue of comparability graphs
Drawing Order Diagrams Through Two-Dimension Extension
Minimum weighted clique cover on claw‐free perfect graphs
On the bi-enhancement of chordal-bipartite probe graphs
Partitioned probe comparability graphs
Lexicographic orientation algorithms
On the thinness and proper thinness of a graph
Independent set under a change constraint from an initial solution
Layered graphs: applications and algorithms
Adjacency matrices of probe interval graphs
Approximation algorithm for the distance-3 independent set problem on cubic graphs
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
On forcibly hereditary P-graphical sequences
Outerstring graphs are $\chi $-bounded
An algorithm for generating all maximal independent subsets of posets
Planar graphs and poset dimension
Bipartite permutation graphs
Stable sets in certain $P_6$-free graphs
Algorithmic aspects of a general modular decomposition theory
Equistable graphs, general partition graphs, triangle graphs, and graph products
A supernodal formulation of vertex colouring with applications in course timetabling
List matrix partitions of graphs representing geometric configurations
Modular decomposition and transitive orientation
The partial gossiping problem
Gallai-like characterization of strong cocomparability graphs
Some results on $(a:b)$-choosability
Polynomial algorithms for the maximum stable set problem on particular classes of $P_{5}$-free graphs
Just-in-time logistics for far-distant suppliers: scheduling truck departures from an intermediate cross-docking terminal
Optimal parallel time bounds for the maximum clique problem on intervals

This page was built for publication: The complexity of comparability graph recognition and coloring

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