Graphs with small bandwidth and cutwidth

F. R.K. Chung, P. D. Seymour

Research output: Contribution to journalArticle

40 Scopus citations

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+c1{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 c2 levels. Is it true that the bandwidth of G can be bounded above by a constant c depending only on c1 and c2?". 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 languageEnglish (US)
Pages (from-to)113-119
Number of pages7
JournalDiscrete Mathematics
Volume75
Issue number1-3
DOIs
StatePublished - May 1989
Externally publishedYes

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