A CONTAGEM DE INTERVALO DE UMA CLASSE DE GRAFOS SPLIT

A complexidade do problema de determinar o menor número de tamanhos distintos de intervalo suficiente para representar um grafo de intervalo, conhecido como contagem de intervalo, está em aberto mesmo para grafos de intervalo split. Dizemos que um intervalo x está aninhado ao intervalo y em um modelo de intervalo se há dois intervalos intersectantes a y, um precedendo e outro sucedendo x no modelo. A profundidade de aninhamento desse modelo é o tamanho da maior cadeia de intervalos aninhados. A profundidade de aninhamento de um grafo de intervalo é a menor profundidade de aninhamento sobre todos os modelos associados, sendo um limite inferior natural para a contagem de intervalo. Cerioli et al. estabeleceram limites para a contagem de
intervalo para subclasses de split, que também limitam a profundidade de aninhamento. Mostramos grafos split para os quais a contagem de intervalo é maior que a profundidade de aninhamento.