Oporowski, Bogdan

Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let $G$ be a finite undirected simple graph.

A \emph{$k$-page book embedding} of $G$ consists of a linear order $\preceq$ of $V(G)$ and a (non-proper) $k$-colouring of $E(G)$ such that edges with the same colour do not cross with respect to $\preceq$. That is, if $v\prec x\prec w\prec y$ for some edges $vw,xy\in E(G)$, then $vw$ and $xy$ receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The \emph{book thickness} of $G$, denoted by bt$(G)$ is the minimum integer $k$ for which there is a $k$-page book embedding of $G$.

Let $G'$ be the graph obtained by subdividing each edge of $G$ exactly once.

\begin{conjecture} There is a function $f$ such that for every graph $G$, $$\text{bt}(G) \leq f( \text{bt}(G') )\enspace.$$ \end{conjecture}

Keywords: book embedding; book thickness

5-coloring graphs with small crossing & clique numbers ★★

Author(s): Oporowski; Zhao

For a graph $G$, we let $cr(G)$ denote the \Def[crossing number]{Crossing number (graph theory)} of $G$, and we let $\omega(G)$ denote the size of the largest complete subgraph of $G$.

\begin{question} Does every graph $G$ with $cr(G) \le 5$ and $\omega(G) \le 5$ have a 5-coloring? \end{question}

Keywords: coloring; crossing number; planar graph

Bounded colorings for planar graphs ★★

Author(s): Alon; Ding; Oporowski; Vertigan

\begin{question} Does there exists a fixed function $f : {\mathbb N} \rightarrow {\mathbb N}$ so that every \Def[planar]{planar graph} graph of maximum degree $d$ has a partition of its vertex set into at most three sets $\{V_1,V_2,V_3\}$ so that for $i=1,2,3$, every component of the graph induced by $V_i$ has size at most $f(d)$? \end{question}

Keywords: coloring; partition; planar graph

Syndicate content