Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Indifference graph
Summary
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
The intersection graphs of unit intervals,
The intersection graphs of sets of intervals no two of which are nested (one containing the other),
The claw-free interval graphs,
The graphs that do not have an induced subgraph isomorphic to a claw K1,3, net (a triangle with a degree-one vertex adjacent to each of the triangle vertices), sun (a triangle surrounded by three other triangles that each share one edge with the central triangle), or hole (cycle of length four or more),
The incomparability graphs of semiorders,
The undirected graphs that have a linear order such that, for every three vertices ordered ––, if is an edge then so are and
The graphs with no astral triple, three vertices connected pairwise by paths that avoid the third vertex and also do not contain two consecutive neighbors of the third vertex,
The graphs in which each connected component contains a path in which each maximal clique of the component forms a contiguous sub-path,
The graphs whose vertices can be numbered in such a way that every shortest path forms a monotonic sequence,
The graphs whose adjacency matrices can be ordered such that, in each row and each column, the nonzeros of the matrix form a contiguous interval adjacent to the main diagonal of the matrix.
The induced subgraphs of powers of chordless paths.
The leaf powers having a leaf root which is a caterpillar.
For infinite graphs, some of these definitions may differ.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.