5
$\begingroup$

ISGCI says that the chromatic number of a graph is upper bounded in terms of the book thickness. https://www.graphclasses.org/classes/par_32.html

This can be improved by saying that the book thickness bounds the degeneracy.

A further improvement would be that the book thickness bounds the acyclic chromatic number.

Is it true? Is there a reference?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

I believe that "book thickness bounds the acyclic chromatic number" was established in this paper:

Dujmovic, Vida, Attila Pór, and David R. Wood. "Track layouts of graphs." Discrete Mathematics and Theoretical Computer Science 6, no. 2 (2004). arXiv abs.

In the Abstract they say,

"As corollaries we prove that acyclic chromatic number is bounded by both queue-number and stack-number."

And then later (Section 5), they say,

"Note that stack-number is also called page-number and book-thickness."

Not sure if this is relevant to your quesiton, but the acyclic chromatic number is not bounded by geometric thickness $\overline{\theta}(G)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The literature can be confusing with four names for the same quantity: book-thickness, page-number, stack-number, and fixed outer-thickness. I would be interested to learn how this proliferation occurred, as book-thickness is ~50 yrs old. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 28, 2020 at 22:58
  • $\begingroup$ Hi Joe. Page-number is descriptive, but does not connect with related topics. Stack-number is used because in some sense it is dual to queue-number. Book-thickness is used to highlight the similarity with thickness (minimum k such that G is the union of k planar graphs). Fixed outer-thickness also make sense, since book-thickness is the minimum k such that G has an edge partition into k outerplanar graphs with a fixed ordering of the vertices. $\endgroup$
    – David Wood
    Commented Apr 29, 2020 at 9:59
  • 1
    $\begingroup$ ... my personal favourite is "convex thickness", since it is really a straight-line drawing with the vertices in convex position. $\endgroup$
    – David Wood
    Commented Apr 29, 2020 at 10:04
  • 1
    $\begingroup$ An indirect answer to the original quesiton is that graphs of bounded book thickness have bounded expansion (in the sense of Nesetril and Ossona de Mendez). So they have bounded generalised colouring numbers. So they have bounded acylic chromatic number. $\endgroup$
    – David Wood
    Commented Apr 29, 2020 at 10:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .