Indifference graph

A weaker notion of width, the clique-width, may be arbitrarily large on indifference graphs.

[11] However, every proper subclass of the indifference graphs that is closed under induced subgraphs has bounded clique-width.

[14] Indifference graphs obey the reconstruction conjecture: they are uniquely determined by their vertex-deleted subgraphs.

The algorithm rounds the points (or interval centers) down to the nearest smaller integer, uses a hash table to find all pairs of points whose rounded integers are within one of each other (the fixed-radius near neighbors problem), and filters the resulting list of pairs for the ones whose unrounded values are also within one of each other.

[17][18][19][20] Once the vertices have been sorted by the numerical values that describe an indifference graph (or by the sequence of unit intervals in an interval representation) the same ordering can be used to find an optimal graph coloring for these graphs, to solve the shortest path problem, and to construct Hamiltonian paths and maximum matchings, all in linear time.

[4] A Hamiltonian cycle can be found from a proper interval representation of the graph in time

[23] However, it is fixed-parameter tractable when parameterized by the total number of colors in the input.

[12] In mathematical psychology, indifference graphs arise from utility functions, by scaling the function so that one unit represents a difference in utilities small enough that individuals can be assumed to be indifferent to it.

[1][24] In bioinformatics, the problem of augmenting a colored graph to a properly colored unit interval graph can be used to model the detection of false negatives in DNA sequence assembly from complete digests.