Mohar, Bojan


List Hadwiger Conjecture ★★

Author(s): Kawarabayashi; Mohar

\begin{conjecture} Every $K_t$-minor-free graph is $c t$-list-colourable for some constant $c\geq1$. \end{conjecture}

Keywords: Hadwiger conjecture; list colouring; minors

Circular choosability of planar graphs

Author(s): Mohar

Let $G = (V, E)$ be a graph. If $p$ and $q$ are two integers, a $(p,q)$-colouring of $G$ is a function $c$ from $V$ to $\{0,\dots,p-1\}$ such that $q \le |c(u)-c(v)| \le p-q$ for each edge $uv\in E$. Given a list assignment $L$ of $G$, i.e.~a mapping that assigns to every vertex $v$ a set of non-negative integers, an $L$-colouring of $G$ is a mapping $c : V \to N$ such that $c(v)\in L(v)$ for every $v\in V$. A list assignment $L$ is a $t$-$(p,q)$-list-assignment if $L(v) \subseteq \{0,\dots,p-1\}$ and $|L(v)| \ge tq$ for each vertex $v \in V$ . Given such a list assignment $L$, the graph G is $(p,q)$-$L$-colourable if there exists a $(p,q)$-$L$-colouring $c$, i.e. $c$ is both a $(p,q)$-colouring and an $L$-colouring. For any real number $t \ge 1$, the graph $G$ is $t$-$(p,q)$-choosable if it is $(p,q)$-$L$-colourable for every $t$-$(p,q)$-list-assignment $L$. Last, $G$ is circularly $t$-choosable if it is $t$-$(p,q)$-choosable for any $p$, $q$. The circular choosability (or circular list chromatic number or circular choice number) of G is $$cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$$

\begin{problem} What is the best upper bound on circular choosability for planar graphs? \end{problem}

Keywords: choosability; circular colouring; planar graphs

Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

\begin{conjecture} Is it possible to color edges of the complete graph $K_n$ using $O(n)$ colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?

Equivalently: is the star chromatic index of $K_n$ linear in $n$? \end{conjecture}

Keywords: complete graph; edge coloring; star coloring

Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index $\chi_s'(G)$ of a graph $G$ is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

\begin{question} Is it true that for every (sub)cubic graph $G$, we have $\chi_s'(G) \le 6$? \end{question}

Keywords: edge coloring; star coloring

Circular colouring the orthogonality graph ★★

Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr

Let ${\mathcal O}$ denote the graph with vertex set consisting of all lines through the origin in ${\mathbb R}^3$ and two vertices adjacent in ${\mathcal O}$ if they are perpendicular.

\begin{problem} Is $\chi_c({\mathcal O}) = 4$? \end{problem}

Keywords: circular coloring; geometric graph; orthogonality

Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

\begin{problem} Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $r > 2$? \end{problem}

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

List colorings of edge-critical graphs ★★

Author(s): Mohar

\begin{conjecture} Suppose that $G$ is a $\Delta$-edge-critical graph. Suppose that for each edge $e$ of $G$, there is a list $L(e)$ of $\Delta$ colors. Then $G$ is $L$-edge-colorable unless all lists are equal to each other. \end{conjecture}

Keywords: edge-coloring; list coloring

Half-integral flow polynomial values ★★

Author(s): Mohar

Let $\Phi(G,x)$ be the flow polynomial of a graph $G$. So for every positive integer $k$, the value $\Phi(G,k)$ equals the number of \Def[nowhere-zero]{nowhere-zero flows} $k$-flows in $G$.

\begin{conjecture} $\Phi(G,5.5) > 0$ for every 2-edge-connected graph $G$. \end{conjecture}

Keywords: nowhere-zero flow

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $P \subseteq {\mathbb R}^2$ is $n$-\emph{universal} if every $n$ vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in $P$, and all edges are (non-intersecting) straight line segments.

\begin{question} Does there exist an $n$-universal set of size $O(n)$? \end{question}

Keywords: geometric graph; planar graph; universal set

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

\begin{conjecture} Let $G$ be the disjoint union of the graphs $G_1$ and $G_2$ and let $\Sigma$ be a surface. Is it true that every optimal drawing of $G$ on $\Sigma$ has the property that $G_1$ and $G_2$ are disjoint? \end{conjecture}

Keywords: crossing number; surface

Syndicate content