Abstract:
It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all Δ ≥ 3 and for all sufficiently large n, there is a simple Δ-regular n-vertex graph with queue-number at least c √ Δ n 1/2-1/Δ for some absolute constant c.

Abstract:
A k-queue layout of a graph G consists of a linear order σ of V(G), and a partition of E(G) into k sets, each of which contains no two edges that are nested in σ. This paper studies queue layouts of graph products and powers

Abstract:
Let G be a graph with chromatic number χ(G). A vertex colouring of G is acyclic if each bichromatic subgraph is a forest. A star colouring of G is an acyclic colouring in which each bichromatic subgraph is a star forest. Let χ a (G) and χ s (G) denote the acyclic and star chromatic numbers of G. This paper investigates acyclic and star colourings of subdivisions. Let G' be the graph obtained from G by subdividing each edge once. We prove that acyclic (respectively, star) colourings of G' correspond to vertex partitions of G in which each subgraph has small arboricity (chromatic index). It follows that χ a (G'), χ s (G') and χ(G) are tied, in the sense that each is bounded by a function of the other. Moreover the binding functions that we establish are all tight. The oriented chromatic number χ → (G) of an (undirected) graph G is the maximum, taken over all orientations D of G, of the minimum number of colours in a vertex colouring of D such that between any two colour classes, all edges have the same direction. We prove that χ → (G')=χ(G) whenever χ(G)≥9.

Abstract:
Let G be a graph with n vertices, with independence number α, and with no K t+1-minor for some t ≥ 5. It is proved that (2α - 1)(2t - 5) ≥ 2n - 5.

Abstract:
Let $G$ be a graph with $n$ vertices, $m$ edges, average degree $delta$, and maximum degree $Delta$. The emph{oriented chromatic number} of $G$ is the maximum, taken over all orientations of $G$, of the minimum number of colours in a proper vertex colouring such that between every pair of colour classes all edges have the same orientation. We investigate the oriented chromatic number of graphs, such as the hypercube, for which $deltageqlog n$. We prove that every such graph has oriented chromatic number at least $Omega(sqrt{n})$. In the case that $deltageq(2+epsilon)log n$, this lower bound is improved to $Omega(sqrt{m})$. Through a simple connection with harmonious colourings, we prove a general upper bound of $Oh{Deltasqrt{n}}$ on the oriented chromatic number. Moreover this bound is best possible for certain graphs. These lower and upper bounds are particularly close when $G$ is ($clog n$)-regular for some constant $c>2$, in which case the oriented chromatic number is between $Omega(sqrt{nlog n})$ and $mathcal{O}(sqrt{n}log n)$.

Abstract:
A \emph{clique} is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with $n$ vertices and $m$ edges; (2) graphs with $n$ vertices, $m$ edges, and maximum degree $\Delta$; (3) $d$-degenerate graphs with $n$ vertices and $m$ edges; (4) planar graphs with $n$ vertices and $m$ edges; and (5) graphs with $n$ vertices and no $K_5$-minor or no $K_{3,3}$-minor. For example, the maximum number of cliques in a planar graph with $n$ vertices is $8(n-2)$.

Abstract:
A \emph{tree-partition} of a graph $G$ is a proper partition of its vertex set into `bags', such that identifying the vertices in each bag produces a forest. The \emph{tree-partition-width} of $G$ is the minimum number of vertices in a bag in a tree-partition of $G$. An anonymous referee of the paper by Ding and Oporowski [\emph{J. Graph Theory}, 1995] proved that every graph with tree-width $k\geq3$ and maximum degree $\Delta\geq1$ has tree-partition-width at most $24k\Delta$. We prove that this bound is within a constant factor of optimal. In particular, for all $k\geq3$ and for all sufficiently large $\Delta$, we construct a graph with tree-width $k$, maximum degree $\Delta$, and tree-partition-width at least $(\eighth-\epsilon)k\Delta$. Moreover, we slightly improve the upper bound to ${5/2}(k+1)({7/2}\Delta-1)$ without the restriction that $k\geq3$.

Abstract:
Hadwiger's Conjecture states that every $K_{t+1}$-minor-free graph is $t$-colourable. It is widely considered to be one of the most important conjectures in graph theory. If every $K_{t+1}$-minor-free graph has minimum degree at most $\delta$, then every $K_{t+1}$-minor-free graph is $(\delta+1)$-colourable by a minimum-degree-greedy algorithm. The purpose of this note is to prove a slightly better upper bound.

Abstract:
The foldings of a connected graph $G$ are defined as follows. First, $G$ is a folding of itself. Let $G'$ be a graph obtained from $G$ by identifying two vertices at distance 2 in $G$. Then every folding of $G'$ is a folding of $G$. The folding number of $G$ is the minimum order of a complete folding of $G$. Theorem: The folding number of every graph equals its chromatic number.

Abstract:
Consider the following relaxation of the Hadwiger Conjecture: For each $t$ there exists $N_t$ such that every graph with no $K_t$-minor admits a vertex partition into $\ceil{\alpha t+\beta}$ parts, such that each component of the subgraph induced by each part has at most $N_t$ vertices. The Hadwiger Conjecture corresponds to the case $\alpha=1$, $\beta=-1$ and $N_t=1$. Kawarabayashi and Mohar [\emph{J. Combin. Theory Ser. B}, 2007] proved this relaxation with $\alpha={31/2}$ and $\beta=0$ (and $N_t$ a huge function of $t$). This paper proves this relaxation with $\alpha={7/2}$ and $\beta=-{3/2}$. The main ingredients in the proof are: (1) a list colouring argument due to Kawarabayashi and Mohar, (2) a recent result of Norine and Thomas that says that every sufficiently large $(t+1)$-connected graph contains a $K_t$-minor, and (3) a new sufficient condition for a graph to have a set of edges whose contraction increases the connectivity.