On the hyperbolicity constant of circular-arc graphs

Autor:	Reyes, R., Rodriguez, J. M., Sigarreta, J. M., Villeta, M.
Rok vydání:	2020
Předmět:	Mathematics - Combinatorics 05C62 05C63 05C10 05C75 05C12
Druh dokumentu:	Working Paper
Popis:	Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves. Comment: arXiv admin note: text overlap with arXiv:1501.02288 by other authors
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2004.01754 Zobrazit plný text záznamu View this record from Arxiv