Can I read Thinness and Its Variations on Some Graph Families and Coloring Graphs of Bounded Thinness on EtoBox?

Thinness and Its Variations on Some Graph Families and Coloring Graphs of Bounded Thinness by Bonomo-Braberman, Flavia; Brandwein, Eric; Oliveira, Fabiano S.; Sampaio, Moysés S.; Sansone, Agustin; Szwarcfiter, Jayme L. is a scholarly article available to read on EtoBox.

What is Thinness and Its Variations on Some Graph Families and Coloring Graphs of Bounded Thinness about?

Interval graphs and proper interval graphs are well known graph classes, for which several generalizations have been proposed in the literature. In this work, we study the (proper) thinness, and several variations, for the classes of cographs, crowns graphs and grid graphs. We provide the exact values for several variants of thinness (proper, independent, complete, precedence, and combinations of them) for the crown graphs $CR_n$. For cographs, we prove that the precedence thinness can be determined in polynomial time. We also improve known bounds for the thinness of $n \times n$ grids $GR_n$ and $m \times n$ grids $GR_{m,n}$, proving that $\left \lceil \frac{n-1}{3} \right \rceil \leq \mbox{thin}(GR_n) \leq \left \lceil \frac{n+1}{2} \right \rceil$. Regarding the precedence thinness, we prove that $\mbox{prec-thin}(GR_{n,2}) = \left \lceil \frac{n+1}{2} \right \rceil$ and that $\left \lceil \frac{n-1}{3} \right \rceil \left \lceil\frac{n-1}{2} \right \rceil + 1 \leq \mbox{prec-thin}(GR_n) \leq \left \lceil\frac{n-1}{2} \right \rceil^2+1$. As applications, we show that the $k$-coloring problem is NP-complete for precedence $2$-thin graphs and for proper $2$-thin graphs, when $k$ is

Author

Bonomo-Braberman, Flavia; Brandwein, Eric; Oliveira, Fabiano S.; Sampaio, Moysés S.; Sansone, Agustin; Szwarcfiter, Jayme L.

Published

2023

Language

EN