Interval degree and bandwidth of a graph
type: Item
instance of: scholarly article
title: Interval degree and bandwidth of a graph
zbMATH Open document ID: 1021.05087
DOI: 10.1016/S0166-218X(02)00574-7
author: Petr A. Golovach
author: Fedor V. Fomin
published in: Discrete Applied Mathematics
publication date: 2003-09-09T00:00:00Z
review text: 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\).
reviewed by: Masakazu Teragaito
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1977902
zbMATH Keywords: interval degree
zbMATH Keywords: interval graph
zbMATH Keywords: bandwidth
zbMATH Keywords: pathwidth
zbMATH Keywords: AT-free claw-free graph
MaRDI profile type: Publication
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: On interval graphs and matrice profiles
cites work: Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Q4871748
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Chordal completions of planar graphs
cites work: Q4780797
cites work: The vertex separation and search number of a graph
cites work: Approximating the bandwidth via volume respecting embeddings
cites work: Q2721963
cites work: Q3328583
cites work: On the powers of graphs with bounded asteroidal number
cites work: The vertex separation number of a graph equals its path-width
cites work: Interval graphs and searching
cites work: Treewidth. Computations and approximations
cites work: Approximating the Bandwidth for Asteroidal Triple-Free Graphs
cites work: Q4251056
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Q3477966
cites work: Triangulating graphs without asteroidal triples
cites work: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
cites work: Graph minors. I. Excluding a forest
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
full work available at URL: s0166-218x(02)00574-7
OpenAlex ID: W2134452793
description: scientific article; zbMATH DE number 1977902