Bounded-Degree Graphs have Arbitrarily Large Queue-Number

Details Bounded-Degree Graphs have Arbitrarily Large Queue-Number Bounded-Degree Graphs have Arbitrarily Large Queue-Number

2006-01-12

arxiv.org/abs/math/0601293v2

Discrete Mathematics & Theoretical Computer Science 10(1):27-34, 2008

Mathematics

Combinatorics

Scientific paper

It is proved that there exist graphs of bounded degree with arbitrarily large
queue-number. In particular, for all $\Delta\geq3$ and for all sufficiently
large $n$, there is a simple $\Delta$-regular $n$-vertex graph with
queue-number at least $c\sqrt{\Delta}n^{1/2-1/\Delta}$ for some absolute
constant $c$.

Affiliated with

Also associated with

No associations

Rating

Bounded-Degree Graphs have Arbitrarily Large Queue-Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounded-Degree Graphs have Arbitrarily Large Queue-Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounded-Degree Graphs have Arbitrarily Large Queue-Number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-495307