Thinness and its variations on some graph families and coloring graphs of bounded thinness

arXiv2303.06070MaRDI QIDQ6509141FDOQ6509141

Moysés S. Jr. Sampaio, Agustín Sansone, Eric Brandwein, Jayme L. Szwarcfiter, Fabiano S. Oliveira, Flavia Bonomo

Abstract: Interval graphs and proper interval graphs are well known graph classes, for which there have been proposed several generalizations in the literature. In this work, we study the (proper) $k$-thin graphs and its variations for the classes of cographs, crown 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 $C{R}_n$. For cographs, we prove that the precedence thinness can be determined in polynomial time. We also improve known bounds for the thinness of $nimesn$ grids $G{R}_n$ and $mimesn$ grids $G{R}_{m,n}$, proving that $leftlceilfracn-13ightceilleqmboxthin(G{R}_n)leqleftlceilfracn+12ightceil$. Regarding the precedence thinness, we prove that $mboxprec-thin(G{R}_{n,2})=leftlceilfracn+12ightceil$ and that $leftlceilfracn-13ightceilleftlceilfracn-12ightceil+1leqmboxprec-thin(G{R}_n)leqleftlceilfracn-12ightcei{l}^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 part of the input. On the positive side, it is polynomially solvable for precedence proper 2-thin graphs, given the order and partition.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

This page was built for publication: Thinness and its variations on some graph families and coloring graphs of bounded thinness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509141)