Relação entre classes de grafos com contagem de intervalo k

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

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

Resumo

A subclasse LEN(a₁,a₂,...,a_k) dos grafos de intervalo consiste daqueles que admitem um modelo de intervalo tendo precisamente os tamanhos de intervalo a₁,a₂,...,a_k. Para todo 0 < a₁ < a₂ <...< a_k e 0 < b₁ < b₂ <...< b_k, provamos que LEN(a₁,a₂,...,a_k) ⊆ LEN(b_1,b₂,...,b_k) se e somente se existe uma constante r tal que b_j = ra_j para todo 1 ≤ j ≤ k.

Palavras-chave: contagem de intervalo, grafo de intervalo, ordem de intervalo

Referências

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.