31 citations · 298 across the 114 of their papers we have counts for
9 papers · 1 filter
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…