Relationship among classes of graphs with interval count k

• Lívia S. Medeiros UERJ
• Fabiano S. Oliveira UERJ
• Jayme L. Szwarcfiter UERJ / UFRJ

DOI: https://doi.org/10.5753/etc.2022.222484

Abstract

The subclass LEN(a₁,a₂,...,a_k) of interval graphs consists of those that admit an interval model having precisely the interval lengths a₁,a₂,...,a_k. For all 0 < a₁ < a₂ < ... < a_k, and 0 < b₁ < b₂ < ... < b_k, we prove that LEN(a₁,a₂,...,a_k) ⊆ LEN(b₁,b₂,...,b_k) if and only if there exists a constant r such that b_j = ra_j forall 1≤ j ≤ k.

Keywords: interval count, interval graph, interval order

References

Fishburn, P. (1985). Interval Orders and Interval Graphs. John Wiley and Sons.

Francis, M. C., Medeiros, L. S., Oliveira, F. S., and Szwarcfiter, J. L. (2022). On subclasses of interval count two and on Fishburn’s conjecture. Discrete Appl. Math., (to appear).

Joos, F., Lowenstein, C., Oliveira, F. S., Rautenbach, D., and Szwarcfiter, J. L. (2014). Graphs of interval count two with a given partition. Inf. Process. Lett., 114:542–546.

Klavík, P., Otachi, Y., and Sejnoha, J. (2019). On the classes of interval graphs of limited nesting and count of lengths. Algorithmica, 81:1490–1511.

Rautenbach, D. and Szwarcfiter, J. L. (2012). Unit and single point interval graphs. Discrete Appl. Math., 160(10):1601–1609.

Skrien, D. (1984). Chronological orderings of interval graphs. Discrete Appl. Math., 8:69–83.