Indifference graph

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals (intervals none of which contains any other one). Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

The finite indifference graphs may be equivalently characterized as

For infinite graphs, some of these definitions may differ.

Because they are special cases of interval graphs, indifference graphs have all the properties of interval graphs; in particular they are a special case of the chordal graphs and of the perfect graphs. They are also a special case of the circle graphs, something that is not true of interval graphs more generally.

In the Erdős–Rényi model of random graphs, an ${\displaystyle n}$-vertex graph whose number of edges is significantly less than ${\displaystyle n^{2/3}}$ will be an indifference graph with high probability, whereas a graph whose number of edges is significantly more than ${\displaystyle n^{2/3}}$ will not be an indifference graph with high probability.

...
Wikipedia