31 citations · 298 across the 114 of their papers we have counts for
9 papers · 2 filters
Obstructions for two-vertex alternating embeddings of graphs in surfaces
Bojan Mohar, Petr Škoda
A class of graphs that lies strictly between the classes of graphs of genus (at most) and is studied. For a fixed orientable surface of genus , let be…
Planar graphs have exponentially many 3-arboricities
Ararat Harutyunyan, Bojan Mohar
It is well-known that every planar or projective planar graph can be 3-colored so that each color class induces a forest. This bound is sharp. In this paper, we show that there are…
Two results on the digraph chromatic number
Ararat Harutyunyan, Bojan Mohar
It is known (Bollobás (1978); Kostochka and Mazurova (1977)) that there exist graphs of maximum degree and of arbitrarily large girth whose chromatic number is at least $c Δ/ \…
Strengthened Brooks Theorem for digraphs of girth three
Ararat Harutyunyan, Bojan Mohar
Brooks' Theorem states that a connected graph of maximum degree has chromatic number at most , unless is an odd cycle or a complete graph. A result of Johansson (199…
Small separations in vertex transitive graphs
Matt DeVos, Bojan Mohar
Let be an integer. We prove a rough structure theorem for separations of order at most in finite and infinite vertex transitive graphs. Let be a vertex transiti…
Minimal obstructions for 1-immersions and hardness of 1-planarity testing
Vladimir P. Korzhik, Bojan Mohar
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non-1-planar gra…
Highly arc-transitive digraphs -- counterexamples and structure
Matt DeVos, Bojan Mohar, Robert Šámal
We resolve two problems of [Cameron, Praeger, and Wormald -- Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica 1993]. First, we construct a loc…
Uniquely D-colourable digraphs with large girth
Ararat Harutyunyan, P. Mark Kayll, Bojan Mohar +1
Let C and D be digraphs. A mapping is a C-colouring if for every arc of D, either is an arc of C or , and the preimage of every vertex o…
Immersing complete digraphs
Matt DeVos, Jessica McDonald, Bojan Mohar +1
We consider the problem of immersing the complete digraph on t vertices in a simple digraph. For Eulerian digraphs, we show that such an immersion always exists whenever minimum de…