Comparability vs Cocomparability

A comparability graph, represented by G(V,E), is a type of graph that is used to model relationships between elements in which the elements can be compared in a transitive manner. The graph is composed of a set of vertices (V) and a set of edges (E) that connect the vertices. The edges in a comparability graph can be directed, meaning that they have a specific direction, such as a → b, indicating that element a is related to element b in a specific way.

The defining characteristic of a comparability graph is that its edge set admits a transitive orientation. This means that if edges a → b and b → c exist, there must also be an edge oriented from a to c. This transitive relationship reflects the ability to compare elements a, b, and c in a consistent manner. For example, in a graph representing a partially ordered set, where a → b means a is greater than b, a → b and b → c implies a > b > c.

Comparability graphs are considered to be perfect, meaning that they have the property of having no induced subgraphs that are odd cycles of length greater than three. This property is closely related to the Weak Perfect Graph Theorem, which states that a graph is perfect if and only if its complement is perfect.

In summary, a comparability graph is a type of graph that is used to model relationships between elements that can be compared in a transitive manner. It is defined by its ability to be directed in a specific way that reflects a transitive relationship between the elements. It is also considered to be perfect and thus abides by the Weak Perfect Graph Theorem. Here you can see an example of a cocomparability graph and if we delete the edge bd, then we get a comparability graph.

A cocomparability graph is a specific type of graph that can be characterized by a particular ordering of its vertices, known as a cocomparability ordering or an umbrella-free ordering.

Given a graph G(V,E), where V is the set of vertices and E is the set of edges, it can be determined whether or not it is a cocomparability graph by examining an ordering σ of the vertices. If for every triple a, b, and c such that a is less than b in the ordering and b is less than c, and if there is an edge between a and c, then there must be an edge between either a and b or b and c, or both.

It is easy to see that an umbrella-free ordering is precisely the same as a transitive orientation of the comparability graph. A comparability graph is a type of graph where there exists an ordering of the vertices such that for any two vertices, one is less than the other. The transitive orientation of a comparability graph is when the edges are directed in a way that preserves the ordering of the vertices, such that if there is an edge between two vertices, the one that is less in the ordering is the starting vertex and the one that is greater is the ending vertex.

A partially ordered set (poset) is a mathematical structure that consists of a set of elements and a binary relation, denoted by ≺, that satisfies certain properties. The set of elements is denoted as V, and the relation ≺ is irreflexive, meaning that an element cannot be related to itself, antisymmetric, meaning that if a ≺ b and b ≺ a then a = b, and transitive, meaning that if a ≺ b and b ≺ c, then a ≺ c.

In a poset, two elements a, b ∈ V are said to be comparable if a ≺ b or b ≺ a, otherwise they are incomparable, denoted by a ∥ b. Because of the transitivity property, if three elements are comparable, for example, a ≺ b, b ≺ c, then a ≺ c. This is precisely what a transitive orientation is in a comparability graph.

A comparability graph is a type of graph where there exists an ordering of the vertices such that for any two vertices, one is less than the other. If G(V,E) is a comparability graph, then it can be represented by a poset P(V,≺) where ab ∈ E if and only if a and b are comparable in P. The transitive orientation of a comparability graph is when the edges are directed in a way that preserves the ordering of the vertices, such that if there is an edge between two vertices, the one that is less in the ordering is the starting vertex and the one that is greater is the ending vertex.

The equivalence between the poset representation and the comparability graph representation gives another way to solve problems for these graph families. Similarly, the equivalence between posets and umbrella-free orderings provides an alternate perspective to study the cocomparability graphs. This allows the use of techniques and results from poset theory to study the properties of cocomparability graphs and vice versa.