Cutwidth and degeneracy of graphsReport as inadecuate

Cutwidth and degeneracy of graphs - Download this document for free, or read online. Document in PDF available to download.

1 IF - Institut Fourier

Abstract : We prove an inequality involving the degeneracy, the cutwidth and the sparsity of graphs. It implies a quadratic lower bound on the cutwidth in terms of the degeneracy for all graphs and an improvement of it for clique-free graphs.

Author: Benoit Kloeckner -



Related documents