# Mohar, Bojan

## Circular choosability of planar graphs ★

Author(s): Mohar

Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is

Problem   What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

## Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

Conjecture   Is it possible to color edges of the complete graph using 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 linear in ?

Keywords: complete graph; edge coloring; star coloring

## Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index of a graph 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.

Question   Is it true that for every (sub)cubic graph , we have ?

Keywords: edge coloring; star coloring

## Circular colouring the orthogonality graph ★★

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

Let denote the graph with vertex set consisting of all lines through the origin in and two vertices adjacent in if they are perpendicular.

Problem   Is ?

## Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

Problem   Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree ?

## List colorings of edge-critical graphs ★★

Author(s): Mohar

Conjecture   Suppose that is a -edge-critical graph. Suppose that for each edge of , there is a list of colors. Then is -edge-colorable unless all lists are equal to each other.

Keywords: edge-coloring; list coloring

## Half-integral flow polynomial values ★★

Author(s): Mohar

Let be the flow polynomial of a graph . So for every positive integer , the value equals the number of nowhere-zero -flows in .

Conjecture   for every 2-edge-connected graph .

Keywords: nowhere-zero flow

## Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set is -universal if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.

Question   Does there exist an -universal set of size ?

Keywords: geometric graph; planar graph; universal set

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

## Matching polynomials of vertex transitive graphs ★★

Author(s): Mohar

Conjecture   For every integer there exists a vertex transitive graph whose matching polynomial has a root of multiplicity at least .

Keywords: matching polynomial; vertex-transitive