### Abstract

We give counter-examples to the following conjecture which arose in the study of small bandwidth graphs. "For a graph G, suppose that {curly logical or}V(G'){curly logical or}≤1+c_{1}{dot operator} diameter (G') for any connected subgraph G' of G, and that G does not contain any refinement of the complete binary tree of c_{2} levels. Is it true that the bandwidth of G can be bounded above by a constant c depending only on c_{1} and c_{2}?". On the other hand, we show that if the maximum degree of G is bounded and G does not contain any refinement of a complete binary tree of a specified size, then the cutwidth and the topological bandwidth of G are also bounded.

Original language | English (US) |
---|---|

Pages (from-to) | 113-119 |

Number of pages | 7 |

Journal | Discrete Mathematics |

Volume | 75 |

Issue number | 1-3 |

DOIs | |

State | Published - May 1989 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Graphs with small bandwidth and cutwidth'. Together they form a unique fingerprint.

## Cite this

Chung, F. R. K., & Seymour, P. D. (1989). Graphs with small bandwidth and cutwidth.

*Discrete Mathematics*,*75*(1-3), 113-119. https://doi.org/10.1016/0012-365X(89)90083-6