The complexity of comparability graph recognition and coloring
From MaRDI portal
Publication:1241524
DOI10.1007/BF02253207zbMath0365.05025OpenAlexW20372564MaRDI QIDQ1241524
Publication date: 1977
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02253207
Related Items (47)
Thinness of product graphs ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs ⋮ Bipartite permutation graphs ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ Stage-graph representations ⋮ The partial gossiping problem ⋮ Planar graphs and poset dimension ⋮ Quasi-threshold graphs ⋮ Adjacency matrices of probe interval graphs ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ On the thinness and proper thinness of a graph ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Independent set under a change constraint from an initial solution ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ An algorithm for generating all maximal independent subsets of posets ⋮ On the thinness of trees ⋮ Comparability digraphs: an analogue of comparability graphs ⋮ Drawing Order Diagrams Through Two-Dimension Extension ⋮ Just-in-time logistics for far-distant suppliers: scheduling truck departures from an intermediate cross-docking terminal ⋮ Distance-\(d\) independent set problems for bipartite and chordal graphs ⋮ The recognition of triangle graphs ⋮ Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs ⋮ Partitioned probe comparability graphs ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ Comparability graphs and intersection graphs ⋮ List matrix partitions of graphs representing geometric configurations ⋮ Optimal parallel time bounds for the maximum clique problem on intervals ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Equistable graphs, general partition graphs, triangle graphs, and graph products ⋮ Comparability graphs and a new matroid ⋮ On the bi-enhancement of chordal-bipartite probe graphs ⋮ On \(H\)-topological intersection graphs ⋮ Layered graphs: applications and algorithms ⋮ On finding a minimum vertex cover of a series-parallel graph ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation ⋮ Some results on \((a:b)\)-choosability ⋮ Algorithmic aspects of a general modular decomposition theory ⋮ On forcibly hereditary P-graphical sequences ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Lexicographic Orientation Algorithms ⋮ Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets ⋮ Modular decomposition and transitive orientation ⋮ Stable sets in certain \(P_6\)-free graphs ⋮ Chronological orderings of interval graphs ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs ⋮ On the edge-integrity of some graphs and their complements ⋮ On the complexity of a family of generalized matching problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Comparability graphs and a new matroid
- Partially ordered sets and their comparability graphs
- Transitiv orientierbare Graphen
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Permutation Graphs and Transitive Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
This page was built for publication: The complexity of comparability graph recognition and coloring
