It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all \Delta ≥ 3 and for all sufﬁciently large n, there is a simple \Delta-regular n-vertex graph with queue-number at least c√\Delta_n^{1/2-1/\Delta} for some absolute constant c.

Source : oai:HAL:hal-00972310v1

Volume: Vol. 10 no. 1

Section: Graph and Algorithms

Published on: January 1, 2008

Submitted on: March 26, 2015

Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 151 times.

This article's PDF has been downloaded 88 times.