On the public citation graph
The complexity of comparability graph recognition and coloring
0 signed · 99 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/bf00967091openalex-snapshot
To the undimmed memory of petr Grigor'evich Kontorovich: Partially ordered sets and their comparability graphs
inferredcites →https://doi.org/10.1016/0095-8956(77)90049-1openalex-snapshot
Comparability graphs and a new matroid
inferredcites →https://doi.org/10.1137/0201013openalex-snapshot
Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
inferredcites →https://doi.org/10.1145/321707.321710openalex-snapshot
Permutation Graphs and Transitive Graphs
inferredcites →https://doi.org/10.4153/cjm-1964-055-5openalex-snapshot
A Characterization of Comparability Graphs and of Interval Graphs
inferredcites →https://doi.org/10.4153/cjm-1971-016-5openalex-snapshot
Transitive Orientation of Graphs and Identification of Permutation Graphs
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/(sici)1099-1360(199606)5:2<81::aid-mcda101>3.0.co;2-vopenalex-snapshot
Preference Structures and Co-comparability Graphs
inferred← citeshttps://doi.org/10.1002/jgt.22157openalex-snapshot
Completing orientations of partially oriented graphs
inferred← citeshttps://doi.org/10.1002/jgt.22611openalex-snapshot
Minimum weighted clique cover on claw‐free perfect graphs
inferred← citeshttps://doi.org/10.1002/jgt.23113openalex-snapshot
Gallai‐like characterization of strong cocomparability graphs
inferred← citeshttps://doi.org/10.1006/jagm.2001.1185openalex-snapshot
Efficient and Practical Algorithms for Sequential Modular Decomposition
inferred← citeshttps://doi.org/10.1007/11828563_10openalex-snapshot
Betweenness and Comparability Obtained from Binary Relations
inferred← citeshttps://doi.org/10.1007/11917496_17openalex-snapshot
Partitioned Probe Comparability Graphs
inferred← citeshttps://doi.org/10.1007/978-1-4613-0303-9_16openalex-snapshot
The Graph Coloring Problem: A Bibliographic Survey
inferred← citeshttps://doi.org/10.1007/978-3-030-68766-3_16openalex-snapshot
Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
inferred← citeshttps://doi.org/10.1007/978-3-031-18530-4_14openalex-snapshot
On the Thinness of Trees
inferred← citeshttps://doi.org/10.1007/978-3-031-30448-4_4openalex-snapshot
Independent Set Under a Change Constraint from an Initial Solution
inferred← citeshttps://doi.org/10.1007/978-3-031-40960-8_5openalex-snapshot
Maximal Ordinal Two-Factorizations
inferred← citeshttps://doi.org/10.1007/978-3-319-45811-3_3openalex-snapshot
Perfect Graphs and Comparability Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-48749-6_20openalex-snapshot
Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-53925-6_18openalex-snapshot
Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-68705-6_13openalex-snapshot
On H-Topological Intersection Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-68705-6_27openalex-snapshot
Extending Partial Representations of Trapezoid Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-71840-8_12openalex-snapshot
Lexicographic Orientation Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-31770-5_21openalex-snapshot
Distance-d Independent Set Problems for Bipartite and Chordal Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-33090-2_58openalex-snapshot
Extending Partial Representations of Function Graphs and Permutation Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-67616-1_27openalex-snapshot
Maengel und Fehlerquellen der Herkoemmlichen Netzplantechnik und Neue Konzepte zu Ihrer Behandlung
inferred← citeshttps://doi.org/10.1007/978-94-009-5315-4_2openalex-snapshot
Algorithmic Aspects of Comparability Graphs and Interval Graphs
inferred← citeshttps://doi.org/10.1007/978-94-009-5315-4_8openalex-snapshot
Parameters of Partial Orders and Graphs: Packing, Covering, and Representation
inferred← citeshttps://doi.org/10.1007/978-94-009-5315-4_9openalex-snapshot
Graphs and Orders in Ramsey Theory and in Dimension Theory
inferred← citeshttps://doi.org/10.1007/978-94-009-7798-3_5openalex-snapshot
Dimension Theory for Ordered Sets
inferred← citeshttps://doi.org/10.1007/bf02237953openalex-snapshot
An algorithm for generating all maximal independent subsets of posets
inferred← citeshttps://doi.org/10.1007/bfb0019427openalex-snapshot
A cleanup on transitive orientation
inferred← citeshttps://doi.org/10.1007/bfb0036950openalex-snapshot
Cutting and partitioning a graph after a fixed pattern
inferred← citeshttps://doi.org/10.1007/s00291-017-0486-yopenalex-snapshot
Just-in-time logistics for far-distant suppliers: scheduling truck departures from an intermediate cross-docking terminal
inferred← citeshttps://doi.org/10.1007/s10479-010-0716-zopenalex-snapshot
A supernodal formulation of vertex colouring with applications in course timetabling
inferred← citeshttps://doi.org/10.1007/s10878-012-9594-4openalex-snapshot
Distance- $$d$$ independent set problems for bipartite and chordal graphs
inferred← citeshttps://doi.org/10.1007/s11083-021-09589-wopenalex-snapshot
Characterization of B0-VPG Cocomparability Graphs and a 2D Visualization of their Posets
inferred← citeshttps://doi.org/10.1016/0012-365x(83)90019-5openalex-snapshot
Comparability graphs and intersection graphs
inferred← citeshttps://doi.org/10.1016/0166-218x(84)90080-5openalex-snapshot
Chronological orderings of interval graphs
inferred← citeshttps://doi.org/10.1016/0166-218x(85)90032-0openalex-snapshot
On the complexity of a family of generalized matching problems
inferred← citeshttps://doi.org/10.1016/0893-9659(89)90075-xopenalex-snapshot
On finding a minimum vertex cover of a series-parallel graph
inferred← citeshttps://doi.org/10.1016/b978-0-12-289260-8.50012-1openalex-snapshot
Comparability Graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2018.03.072openalex-snapshot
On the thinness and proper thinness of a graph
inferred← citeshttps://doi.org/10.1016/j.dam.2019.01.013openalex-snapshot
List matrix partitions of graphs representing geometric configurations
inferred← citeshttps://doi.org/10.1016/j.disc.2023.113829openalex-snapshot
Comparability digraphs: An analogue of comparability graphs
inferred← citeshttps://doi.org/10.1016/j.ijar.2026.109734openalex-snapshot
DimFlux: Force-directed additive line diagrams
inferred← citeshttps://doi.org/10.1016/j.jalgor.2003.11.005openalex-snapshot
Parallel algorithms for P4-comparability graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.01.038openalex-snapshot
Partitioned probe comparability graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.07.012openalex-snapshot
Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
inferred← citeshttps://doi.org/10.1016/s0012-365x(96)00177-xopenalex-snapshot
On semi-P4-sparse graphs
inferred← citeshttps://doi.org/10.1016/s0012-365x(98)00319-7openalex-snapshot
Modular decomposition and transitive orientation
inferred← citeshttps://doi.org/10.1016/s0020-0190(96)00197-4openalex-snapshot
Polynomial algorithms for the maximum stable set problem on particular classes of P5-free graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(87)80003-3openalex-snapshot
Bipartite permutation graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(96)00080-7openalex-snapshot
Stage-graph representations
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00046-3openalex-snapshot
Stable sets in certain P6-free graphs
inferred← citeshttps://doi.org/10.1016/s0167-5060(08)70820-3openalex-snapshot
Approximative Algorithms for Discrete Optimization Problems
inferred← citeshttps://doi.org/10.1016/s0304-0208(08)72454-xopenalex-snapshot
Scheduling Problems with a Singular Solution
inferred← citeshttps://doi.org/10.1016/s0304-0208(08)72942-6openalex-snapshot
Algorithmic Aspects of Perfect Graphs
inferred← citeshttps://doi.org/10.1016/s1571-0653(05)80062-9openalex-snapshot
Linear-time Algorithms for Maximum Sets of Sources and sinks
inferred← citeshttps://doi.org/10.1023/a:1005803107931openalex-snapshot
Sources and Sinks in Comparability Graphs
inferred← citeshttps://doi.org/10.1038/s41598-021-00281-yopenalex-snapshot
Spatial representability of neuronal activity
inferred← citeshttps://doi.org/10.1051/ita/2011106openalex-snapshot
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
inferred← citeshttps://doi.org/10.1051/ita/2024004openalex-snapshot
Human-verifiable proofs in the theory of word-representable graphs
inferred← citeshttps://doi.org/10.1080/0740817x.2015.1056390openalex-snapshot
Just-in-time vehicle scheduling with capacity constraints
inferred← citeshttps://doi.org/10.1109/iadcc.2018.8692129openalex-snapshot
Hard Problems on Layered Graphs: Parallel Algorithms and Improvements
inferred← citeshttps://doi.org/10.1109/proc.1980.11899openalex-snapshot
Frequency assignment: Theory and applications
inferred← citeshttps://doi.org/10.1109/tcst.2017.2692204openalex-snapshot
Prototyping of Concurrent Control Systems With Application of Petri Nets and Comparability Graphs
inferred← citeshttps://doi.org/10.1137/0214048openalex-snapshot
On Comparability and Permutation Graphs
inferred← citeshttps://doi.org/10.1137/17m1157374openalex-snapshot
Outerstring Graphs are $\chi$-Bounded
inferred← citeshttps://doi.org/10.1145/2745754.2745779openalex-snapshot
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication
inferred← citeshttps://doi.org/10.1145/58562.59300openalex-snapshot
Incremental modular decomposition
inferred← citeshttps://doi.org/10.1145/800061.808777openalex-snapshot
Transitive orientation in 0(n 2 ) time
inferred← citeshttps://doi.org/10.1287/mnsc.39.1.115openalex-snapshot
Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem
inferred← citeshttps://doi.org/10.1287/moor.8.2.170openalex-snapshot
A Fast Algorithm for the Decomposition of Graphs and Posets
inferred← citeshttps://doi.org/10.1287/opre.32.1.89openalex-snapshot
Minimizing Costs of Resource Requirements in Project Networks Subject to a Fixed Completion Time
inferred← citeshttps://doi.org/10.1287/opre.44.5.775openalex-snapshot
Shop Problems with two Machines and Time Lags
inferred← citeshttps://doi.org/10.1504/ijor.2009.026940openalex-snapshot
Scheduling with undirected graphs: motivations and reviews
inferred← citeshttps://doi.org/10.1587/transfun.2021dmp0017openalex-snapshot
Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
inferred← citeshttps://doi.org/10.33774/coe-2024-k5zl3-v2openalex-snapshot
Note for the P versus NP Problem (II)
inferred← citeshttps://doi.org/10.3390/a11070093openalex-snapshot
Layered Graphs: Applications and Algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.1503.02773openalex-snapshot
Simpler, Linear-Time Transitive Orientation via Lexicographic Breadth-First Search
inferred← citeshttps://doi.org/10.48550/arxiv.2110.05405openalex-snapshot
Human-verifiable proofs in the theory of word-representable graphs
inferred← citeshttps://doi.org/10.5445/ir/1000007159openalex-snapshot
Algorithmic Aspects of Triangle-Based Network Analysis
inferred← citeshttps://doi.org/10.5555/314161.314172openalex-snapshot
Linear-time transitive orientation
inferred← citeshttps://doi.org/10.5555/314464.314641openalex-snapshot
Linear-time modular decomposition and efficient transitive orientation of comparability graphs
inferred← citeshttps://doi.org/10.7151/dmgt.2494openalex-snapshot
An analogue of quasi-transitivity for edge-coloured graphs
inferred← citeshttps://doi.org/10.7155/jgaa.00645openalex-snapshot
Drawing Order Diagrams Through Two-Dimension Extension
inferred← citeshttps://doi.org/10.7916/d89z9bzkopenalex-snapshot
Forbidden Substructures in Graphs and Trigraphs, and Related Coloring Problems
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.