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

A graph \(G\) is an interval graph if there is a mapping of \(V(G)\) on intervals of the real line, each \(v\in V(G)\) corresponding to the interval \(I_v\), such that \((u,v)\in E(G)\) if and only if \(I_u\cap I_v\neq \emptyset\) for all distinct \(u,v\in V(G)\). \(G\) is called proper interval graph if there is such a mapping of vertices to intervals such that \(I_u\nsubseteq I_v\) for all distinct \(u,v\in V(G)\). It is well known that (see [\textit{S. Olariu}, Inf. Process. Lett. 37, No. 1, 21--25 (1991; Zbl 0711.68083)]):\N\NTheorem 1. A graph \(G\) is an interval graph if and only if there is an ordering \(\sigma\) of \(V(G)\) such that, for any triple \((p,q,r)\) of vertices of \(V(G)\) ordered according to \(\sigma\), if \((p,q)\in E(G)\), then \((q,r)\in E(G)\).\N\NThe ordering \(\sigma\) in Theorem \(1\) is called canonical. A similar result holds for proper interval graphs (see [\textit{F. S. Roberts}, in: Recent progress in combinatorics. Proceedings of the third Waterloo conference on combinatorics, May 1968. New York-London: Academic Press. 301--310 (1969; Zbl 0193.24301)]):\N\NTheorem 2. A graph \(G\) is a proper interval graph if there is an ordering \(\sigma\) of \(V(G)\) for which \(\sigma\) and its reversal are both canonical.\N\NThese definitions are generalized in the following way. A \(k\)-thin graph \(G\) is a graph for which there exist a \(k\)-partition \(\mathcal V=(V_1,\dots,V_k)\) of \(V(G)\) and on ordering \(\sigma\) of \(V(G)\) such that, for any triple \((p,q,r)\) of vertices of \(V(G)\) ordered according to \(\sigma\), if \(p,q\in V_i\) for some \(i\in\{1,\dots,k\}\) and \((p,r)\in E(G)\), then \((q,r)\in E(G)\). Such an ordering \(\sigma\) is said to be consistent with \(\mathcal V\). A graph \(G\) is called a proper \(k\)-thin graph if \(V(G)\) admits a \(k\)-partition \(\mathcal V\) of \(V(G)\) and an ordering \(\sigma\) such that both \(\sigma\) and its reversal are consistent with \(\mathcal V\). An ordering of this type is said to be strongly consistent with \(\mathcal V\).\N\NWhile not all graphs are (proper) interval graphs, any graph is \(k\)-thin for some \(k\ge 1\), since we could take \(k=|V(G)|\). Moreover, (proper) \(1\)-thin graphs are precisely (proper) interval graphs.\N\NThe thinness (resp. proper thinness) of a graph \(G\), denoted by thin\((G)\) (resp. pthin\((G)\)) is the minimum value \(k\) for which \(G\) is a \(k\)-thin graph (resp. proper \(k\)-thin graph). Other variations of thinness are considered in this paper, such as, for example, (proper) precedence, independent, complete, and combinations of these.\N\NIn this paper, the authors provide the exact value of several variants of thinness for the crown graph, which is obtained from the complete bipartite graph \(K_{n,n}\) by removing a perfect matching. They improve known upper and lower bounds for the thinness of the grid graph \(GR_n\), which is the Cartesian product of two paths of length \(n-1\). They also prove that for cographs, which can be defined as the graphs obtained from trivial graphs by the union and join operations, the precedence thinness can be determined in polynomial time.\N\NAs applications, they show that the \(k\)-coloring problem is NP-complete for precedence \(2\)-thin graphs and for proper \(2\)-thin graphs, while it is polynomially solvable for precedence proper \(2\)-thin graphs, given the order and the partition.