Graph bandwidth: Difference between revisions

Revision as of 23:51, 17 January 2015

Revision as of 18:07, 18 January 2015

Line 22:

The bandwidth of a graph can be bounded in terms of various other graph parameters. For instance, letting χ(''G'') denote the [[chromatic number]] of ''G'',

:φ(''G'') ≥ χ(''G'')- − 1;

letting diam(''G'') denote the [[diameter (graph theory)|diameter]] of ''G'', the following inequalities hold:<ref>{{harvnb|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>

:<math>\lceil (n-1)/\mathrm{diam}(G) \rceil \le \varphi(G) \le n - \mathrm{diam}(G)</math>,