Interval degree and bandwidth of a graph (Q1406031): Difference between revisions

A graph is called an interval graph if its vertices can be assigned intervals on the real line so that the vertices are adjacent if and only if the corresponding intervals intersect. Some interesting graph parameters can be defined in terms of interval supergraphs. For example, the pathwidth \(\text{pw}(G)\) of a graph \(G\), which was introduced by \textit{N. Robertson} and \textit{P. Seymour} [J. Comb. Theory, Ser. B 35, 39-61 (1983; Zbl 0521.05062)], can be defined as the smallest clique number of interval supergraphs of \(G\) decreased by one. In the same manner the authors introduce a new graph parameter, the interval degree \(\text{id}(G)\), as the smallest max-degree of vertices of interval supergraphs of \(G\). They show the inequality \(\text{id}(G)/2 \leq \text{bw}(G) \leq \text{id}(G)\) for any graph \(G\), where \(\text{bw}(G)\) denotes the bandwidth of \(G\). This lower bound for the bandwidth improves the well-known one, the half of the maximum vertex degree. In fact, these bounds are shown to be best possible. Also, they show that \(\text{pw}(G^2) \leq \text{id}(G)\) holds for any graph \(G\), which is also best possible. An asteroidal triple in a graph is a set of three vertices such that for any two of these vertices there exists a path joining them that avoids the closed neighborhood of the third. A graph is said to be AT-free if it contains no asteroidal triple. A graph isomorphic to \(K_{1,3}\) is called a claw, and a graph is said to be claw-free if it contains no induced claw. Then, the authors show that \(\text{id}(G)\) is equal to the clique number of \(G^2\) minus one, when \(G\) is AT-free claw-free. Finally, it is shown that there is a polynomial time algorithm for computing \(\text{id}(G)\) for AT-free claw-free graphs \(G\).