A natural unit interval graph on the ordered vertices is a graph specified by weakly increasing integers , ..., with , having edges exactly when . The specified ordering of the vertices is part of this convention. For the graph has no edges, while gives the complete graph. Choosing gives a path graph. Its chromatic quasisymmetric function is symmetric in the color variables, and its elementary expansion is the subject of the Shareshian-Wachs conjecture.

This graph is the incomparability graph of the unit interval order on in which strictly precedes exactly when . Its edges join precisely the pairs that are incomparable in this partial order.

See also

Chromatic Quasisymmetric Function, Shareshian-Wachs Conjecture

Explore with Wolfram|Alpha

References

Shareshian, J. and Wachs, M. L. "Chromatic Quasisymmetric Functions." Adv. Math. 295, 497-551, 2016. https://doi.org/10.1016/j.aim.2015.12.018.

Cite this as:

Weisstein, Eric W. "Natural Unit Interval Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NaturalUnitIntervalGraph.html

Subject classifications