What is comparability?


In mathematics, any two elements x and y of a set P that is partially ordered by a binary relation ≤ are comparable when either xy or yx. If it is not the case that x and y are comparable, then they are called incomparable.

Read more about Comparability.

Some articles on comparability:

Comparability Graph - Algorithms
... to the edges of any graph, so to complete the task of testing whether a graph is a comparability graph, one must test whether the resulting orientation is transitive, a problem ... Because comparability graphs are perfect, many problems that are hard on more general classes of graphs, including graph coloring and the independent set problem, can be computed in ...
Dilworth's Theorem - Perfection of Comparability Graphs
... A comparability graph is an undirected graph formed from a partial order by creating a vertex per element of the order, and an edge connecting any two comparable elements ... Thus, a clique in a comparability graph corresponds to a chain, and an independent set in a comparability graph corresponds to an antichain ... Any induced subgraph of a comparability graph is itself a comparability graph, formed from the restriction of the partial order to a subset of its elements ...