31 citations · 298 across the 114 of their papers we have counts for
7 papers · 1 filter
Integral Cayley multigraphs over Abelian and Hamiltonian groups
Matt DeVos, Roi Krakovski, Bojan Mohar +1
It is shown that a Cayley multigraph over a group with generating multiset is integral (i.e., all of its eigenvalues are integers) if lies in the integral cone over the…
5-list-coloring planar graphs with distant precolored vertices
Zdenek Dvorak, Bernard Lidicky, Bojan Mohar +1
We answer positively the question of Albertson asking whether every planar graph can be -list-colored even if it contains precolored vertices, as long as they are sufficiently f…
Obstructions of Connectivity 2 for Embedding Graphs into the Torus
Bojan Mohar, Petr Škoda
The complete set of minimal obstructions for embedding graphs into the torus is still not determined. In this paper, we present all obstructions for the torus of connectivity 2. Fu…
A note on forbidding clique immersions
Matt DeVos, Jessica McDonald, Bojan Mohar +1
Robertson and Seymour proved that the relation of graph immersion is well-quasi-ordered for finite graphs. Their proof uses the results of graph minors theory. Surprisingly, there…
Adding one edge to planar graphs makes crossing number and 1-planarity hard
Sergio Cabello, Bojan Mohar
A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar gra…
5-choosability of graphs with crossings far apart
Zdenek Dvorak, Bernard Lidicky, Bojan Mohar
We give a new proof of the fact that every planar graph is 5-choosable, and use it to show that every graph drawn in the plane so that the distance between every pair of crossings…
Spectrum of Cayley graphs on the symmetric group generated by transpositions
Roi Krakovski, Bojan Mohar
For an integer , let be the Cayley graph on the symmetric group generated by the set of transpositions . It is shown that the spectrum…