31 citations · 298 across the 114 of their papers we have counts for
11 papers · 1 filter
The genus of a random bipartite graph
Yifan Jing, Bojan Mohar
Archdeacon and Grable (1995) proved that the genus of the random graph is almost surely close to if . In this paper…
Notes on Cops and Robber game on graphs
Bojan Mohar
These are some personal notes about the pursuit game of Cops and Robbers that I made starting in 2007. More old and new problems (and some solutions) will be added in future versio…
Maximum number of colourings. II. 5-chromatic graphs
Fiachra Knox, Bojan Mohar
In 1971, Tomescu conjectured [Le nombre des graphes connexes -chromatiques minimaux aux sommets étiquetés, C. R. Acad. Sci. Paris 273 (1971), 1124--1126] that every connected gr…
Topological directions in Cops and Robbers
Anthony Bonato, Bojan Mohar
We survey results at the intersection of topological graph theory and the game of Cops and Robbers, focusing on results, conjectures, and open problems for the cop number of a grap…
Maximum number of colourings. I. 4-chromatic graphs
Fiachra Knox, Bojan Mohar
It is proved that every connected graph on vertices with has at most -colourings for every . Equality holds for some (an…
Finding a subdivision of a prescribed digraph of order 4
Frédéric Havet, A. Karolinna Maia, Bojan Mohar
The problem of when a given digraph contains a subdivision of a fixed digraph is considered. Bang-Jensen et al. laid out foundations for approaching this problem from the algor…
Exponentially many nowhere-zero -, -, and -flows
Zdeněk Dvořák, Bojan Mohar, Robert Šámal
We prove that, in several settings, a graph has exponentially many nowhere-zero flows. These results may be seen as a counting alternative to the well-known proofs of existence of…
Whitney's Theorem for 2-Regular Planar Digraphs
Dan Archdeacon, Matt DeVos, Stefan Hannie +1
A digraph is 2-regular if every vertex has both indegree and outdegree two. We define an embedding of a 2-regular digraph to be a 2-cell embedding of the underlying graph in a clos…
Embedding Quartic Eulerian Digraphs on the Plane
Dan Archdeacon, Paul Bonnington, Bojan Mohar
Minimal obstructions for embedding 4-regular Eulerian digraphs on the plane are considered in relation to the partial order defined by the cycle removal operation. Their basic prop…
The structure of ABC-minimal trees with given number of leaves
Bojan Mohar
The atom-bond connectivity (ABC) index is a degree-based molecular descriptor with diverse chemical applications. Recent work of Lin et al. [W. Lin, J. Chen, C. Ma, Y. Zhang, J. Ch…
Colourings with Bounded Monochromatic Components in Graphs of Given Circumference
Bojan Mohar, Bruce Reed, David R. Wood
We prove that every graph with circumference at most is -colourable such that every monochromatic component has size at most . The bound on the num…