Home » Author index

Mohar, Bojan


Graph Theory » Coloring » Vertex coloring

List Hadwiger Conjecture ★★

Author(s): Kawarabayashi; Mohar

Conjecture   Every $ K_t $-minor-free graph is $ c t $-list-colourable for some constant $ c\geq1 $.

Keywords: Hadwiger conjecture; list colouring; minors

Posted by David Wood
updated July 7th, 2014
add new comment
Graph Theory » Coloring » Homomorphisms

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}\}.$$

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

Keywords: choosability; circular colouring; planar graphs

Posted by rosskang
updated August 23rd, 2012
add new comment
Graph Theory

Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

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 $?

Keywords: complete graph; edge coloring; star coloring

Posted by Robert Samal
updated November 16th, 2010
add new comment
Graph Theory

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.

Question   Is it true that for every (sub)cubic graph $ G $, we have $ \chi_s'(G) \le 6 $?

Keywords: edge coloring; star coloring

Posted by Robert Samal
updated November 16th, 2010
add new comment
Graph Theory » Coloring » Vertex 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.

Problem   Is $ \chi_c({\mathcal O}) = 4 $?

Keywords: circular coloring; geometric graph; orthogonality

Posted by mdevos
updated September 28th, 2009
4 comments
Graph Theory » Infinite Graphs

Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

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

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

Posted by Robert Samal
updated July 24th, 2007
add new comment
Graph Theory » Coloring » Edge coloring

List colorings of edge-critical graphs ★★

Author(s): Mohar

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.

Keywords: edge-coloring; list coloring

Posted by Robert Samal
updated June 12th, 2007
add new comment
Graph Theory » Algebraic G.T.

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 nowhere-zero $ k $-flows in $ G $.

Conjecture   $ \Phi(G,5.5) > 0 $ for every 2-edge-connected graph $ G $.

Keywords: nowhere-zero flow

Posted by mohar
updated May 31st, 2007
add new comment
Graph Theory » Topological G.T. » Drawings

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $ P \subseteq {\mathbb R}^2 $ is $ n $-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.

Question   Does there exist an $ n $-universal set of size $ O(n) $?

Keywords: geometric graph; planar graph; universal set

Posted by mdevos
updated May 22nd, 2007
add new comment
Graph Theory » Topological G.T. » Crossing numbers

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

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?

Keywords: crossing number; surface

Posted by mdevos
updated September 30th, 2007
1 comment
Syndicate content