arXiv Analytics

Sign in

arXiv:0907.5138 [math.CO]AbstractReferencesReviewsResources

Cutwidth and degeneracy of graphs

Benoit Kloeckner

Published 2009-07-29, updated 2010-10-29Version 2

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.

Comments: v2: slightly shortened, some typos corrected.
Categories: math.CO, cs.DM
Related articles: Most relevant | Search more
arXiv:math/0512400 [math.CO] (Published 2005-12-16, updated 2007-07-23)
A quadratic lower bound for colourful simplicial depth
arXiv:2406.03561 [math.CO] (Published 2024-06-05)
Energy of a graph and Randić index of subgraphs
arXiv:2405.17639 [math.CO] (Published 2024-05-27)
Some new Bollobás-type inequalities

Links

Toolbox