Thinness in Chordal Graphs
Abstract
The thinness of a graph is a measure of "how distant" the graph is from an interval graph, which are exactly the graphs with thinness 1. In this paper we introduce an analogous concept, the chordal thinness, presenting upper bounds and partial results concerning its computational complexity. Moreover, we determine the complexity of some classic problems in graphs of bounded chordal thinness. In particular, we show that INDEPENDENT SET remains NP-Hard even in graphs of chordal thinness 3. On the other hand, we show that it is possible to generalize the polinomiality result of CLIQUE from chordal graphs to graphs with chordal thinness 2.
Keywords:
Algorithms, Computational Complexity, Graph Theory and Combinatorics
References
Bonomo-Braberman, F. and Brito, G. A. (2021). Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs.
de Estrada, D. (2020). On the thinness and proper thinness of a graph. Discrete Applied Mathematics 261.
Mannino, C. (2007). The stable set problem and the thinness of a graph. Operations Research Letters.
Rose, D. J. and Tarjan, R. E. (1978). Algorithmic aspects of vertex elimination on directed graphs. SIAM Journal on Applied Mathematics, 34(1):176–197.
de Estrada, D. (2020). On the thinness and proper thinness of a graph. Discrete Applied Mathematics 261.
Mannino, C. (2007). The stable set problem and the thinness of a graph. Operations Research Letters.
Rose, D. J. and Tarjan, R. E. (1978). Algorithmic aspects of vertex elimination on directed graphs. SIAM Journal on Applied Mathematics, 34(1):176–197.
Published
2022-07-31
How to Cite
AMORIM, Bernardo; SANTOS, Vinicius F. dos.
Thinness in Chordal Graphs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 73-76.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.223033.
