CanaDAM 2013
Université Memorial de Terre-Neuve, 10 - 13 juin 2013

Graph Theory
Responsable et président: Matthias Kriesell (Universität Hamburg)

JOHANNES CARMESIN, Universität Hamburg
Canonical tree decomposition into highly connected pieces  [PDF] [SLIDES]

We consider the question how to decompose a graph canonically into highly connected pieces. First we discuss what might be a good notion for highly connected pieces and then we talk about how to get these canonical decompositions.

BOJAN MOHAR, Simon Fraser University
On median eigenvalues of graphs  [PDF]

Median eigenvalues of a graph are closely related to the HOMO-LUMO separation properties from mathematical chemistry. The talk will give an overview of recent results about the median eigenvalues. One particular surprising discovery is that the median eigenvalues of every connected bipartite graph G of maximum degree at most three belong to the interval [-1,1] with a single exception of the Heawood graph, whose median eigenvalues are $\pm\sqrt{2}$. Moreover, if G is not isomorphic to the Heawood graph, then a positive fraction of its median eigenvalues lie in the interval [-1,1].

JONATHAN NOEL, McGill University
Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond  [PDF] [SLIDES]

Choosability is a well-studied variant of graph colouring. The \emph{choice number} $\text{ch}(G)$ of a graph $G$ is the minimum $k$ such that for any assignment of lists of size $k$ to the vertices of $G$, there is a proper colouring in which every vertex is coloured with an element of its list.

Although $\text{ch}$ is not bounded above by any function of $\chi$ in general, one can still consider the relationship between $\text{ch}$ and $\chi$ for restricted families of graphs. We discuss recent results and open problems regarding the choice number of graphs of bounded order (with respect to $\chi$).

ROBERT ŠÁMAL, Charles University
Cycle-continuous mappings -- order structure  [PDF] [SLIDES]

Given two graphs, a mapping between their edge-sets is \emph{cycle-continuous}, if the preimage of every cycle is a cycle. This is motivated by Jaeger's conjecture: every bridgeless graph has a cycle-continuous mapping to the Petersen graph. Answering a question of DeVos, Nešetřil, and Raspaud, we prove that there is an infinite set of graphs with no cycle-continuous mapping between them. Extending this result, we show that every countable poset can be represented by graphs and existence of cycle-continuous mappings between them. We utilize construction of snarks by repeated 3-joins and a result of Hubička and Nešetřil on homomorphisms of paths.

GÁBOR SIMONYI, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences
Comparing the local chromatic number of a digraph and its underlying undirected graph  [PDF] [SLIDES]

The local chromatic number of a graph was introduced in 1986 and its natural generalization to directed graphs in 2005. Here we investigate the relation of the local chromatic number of an oriented graph to that of its underlying undirected graph. We show the existence of a graph where the two values differ for any orientation. We prove that the opposite is true for fractional versions. Thus the minimum possible ratio of these two fractional parameters is $1$. We also determine the largest possible ratio of these two invariants. Joint work with G\'abor Tardos and Ambrus Zsb\'an.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Memorial de Terre-Neuve