---
tag: 1P4830BH6Z
kind: concept
name: Comparability graph
msc: [05C75, 06A07, 05C17]
sources:
  - url: https://en.wikipedia.org/wiki/Comparability_graph
same_as:
  wikidata: Q5155607
  wikipedia: Comparability graph
---

## Summary

The comparability graph of a [[partially ordered set|0QV2JS9RJ3]] joins two elements by an edge when they are comparable.
A graph is a comparability graph when it arises in this way from some partial order.
Chains become cliques and antichains become independent sets, so order results such as [[Mirsky's theorem|5VPXR3RDF1]] turn into graph results.
Comparability graphs are [[perfect graphs|1YZ7NV161A]].

## Explanations

### L1 human

Start from a poset and forget which element is the smaller one in each related pair.
What remains is an ordinary [[graph|00C0BR7D7H]]: an edge just says "these two are related".
For the divisors of $6$, the graph has edges $1$–$2$, $1$–$3$, $1$–$6$, $2$–$6$ and $3$–$6$, but no edge $2$–$3$.