Recent publications and preprints by Bojan Mohar

Papers that have already been published are available in their original form (which is usually rather close to their published form).

Some PDF files can be accessed directly from this page. If a copy of a copyrighted file is provided, it can only be downloaded and used for academic purposes. Please contact B.M. if in doubt.

Papers in print or submitted

  1. K.-I. Kawarabayashi, B. Mohar, Approximating the list-chromatic number in minor-closed classes of graphs, submitted to TCS, 2006.[Electronic access][PDF file]
  2. T. Bohme, K.-I. Kawarabayashi, J. Maharry, B. Mohar, K3,k-minors in large 7-connected graphs, submitted to JCTB, May 2008. [PDF file]
  3. G. Fijavz, B. Mohar, D. Scheide, Acyclic edge-colorings of planar and arbitrary degenerate graphs, submitted, April 2010.
  4. Matt DeVos, Bojan Mohar, Small separations in vertex transitive graphs, Forum. Math. sigma, submitted, 2012. [Electronic access][arXiv]
  5. Bojan Mohar, Petr Skoda, Obstructions for two-vertex alternating embeddings of graphs in surfaces, submitted to EJC, 2012. [Electronic access][arXiv]
  6. Matt DeVos, Bojan Mohar, Robert Samal, Highly arc-transitive digraphs - structure and counterexamples, Combinatorica, in print. [Electronic access][arXiv]
  7. Zdenvek Dvorak, Bernard Lidicky, Bojan Mohar, 5-choosability of graphs with crossings far apart, submitted to JCTB, January 2012. [Electronic access][arXiv]
  8. Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar, Bruce Reed, Flat embeddings in 3-space in linear time, submitted. [Electronic access][arXiv]
  9. Bojan Mohar, Petr Skoda, Discharging proofs made easy, submitted. [Electronic access][arXiv]
  10. Zdenek Dvorak, Bernard Lidicky, Bojan Mohar, Luke Postle, 5-list-coloring planar graphs with distant precolored vertices, submitted to JCTB, September 2012. [Electronic access][arXiv]
  11. Ararat Harutyunyan, Bojan Mohar, Planar digraphs of digirth five are 2-colorable, submitted to J. Graph Theory, December 2012.
  12. Bojan Mohar, Median eigenvalues of bipartite subcubic graphs, CPC, in print. [Online access][arXiv]
  13. Bojan Mohar, Colouring graphs on surfaces, chapter for Selected Topics in Graph Theory monograph, June 2013, appeared. [Online access][arXiv]
  14. Pavol Hell, Bojan Mohar, Arash Rafiey, Ordering without forbidden patterns, submitted, July 2013.
  15. Frederic Havet, A. Karolinna Maia, Bojan Mohar, Finding a subdivision of a prescribed digraph, submitted, July 2013.
  16. Zdenek Dvorak, Bojan Mohar, Crossing numbers of periodic graphs, accepted to JGT. arXiv: 1405.5117
  17. Bojan Mohar, Petr Skoda, Cascades and obstructions of low connectivity for embedding graphs into the Klein bottle, submitted to JCTB, June 2014. arXiv: 1406.1341
  18. Lino Demasi, Bojan Mohar, Four terminal planar Delta-Wye reducibility via rooted $K_{2,4}$ minors, "Proc. Twenty-Sixth Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015'', pp. 1728--1742, 2015. \url{}, doi: 10.1137/1.9781611973730.115
  19. Bojan Mohar, Arash Rafiey, Behruz Tayfeh-Rezaie, and Hehui Wu, Interval minors of complete bipartite graphs, JGT, in press. arXiv: 1408.1155
  20. Pavol Hell, Bojan Mohar, Arash Rafiey, Ordering without forbidden patterns, submitted to JGT. arXiv: 1408.1461
  21. Seyed Saeed Changiz Rezaei, Seyyed Aliasghar Hosseini, Bojan Mohar, Cubic normal graphs, submitted, October 2014.
  22. Bernardo M. Abrego, Oswin Aichholzer, Silvia Fernandez-Merchant, Dan McQuillan, Bojan Mohar, Petra Mutzel, Pedro Ramos, R. Bruce Richter, and Birgit Vogtenhuber, Bishellable drawings of $K_n$, submitted to El-JC, October 2015. arXiv: 1510.00549.
  23. Bojan Mohar, Hehui Wu, Dichromatic number and fractional chromatic number, submitted, January 2015.
  24. Sergio Cabello, Bojan Mohar, Robert Samal, Drawing a disconnected graph on the torus, Eurocomb 2015.
  25. Bojan Mohar, Hehui Wu, Triangle-free subgraphs with large fractional chromatic number, Eurocomb 2015. doi: 10.1016/j.endm.2015.06.089
  26. Ross Churchley, Bojan Mohar, and Hehui Wu, Weak duality for packing edge-disjoint odd (u, v)-trails, SODA 2016; accepted.
  27. Krystal Guo, Bojan Mohar, Hermitian adjacency matrix of digraphs and mixed graphs, submitted to JGT, May 2015. arXiv: 1505.01321.
  28. Bojan Mohar, Hermitian adjacency spectrum and switching equivalence of mixed graphs, Linear Algebra Appl., accepted. doi: 10.1016/j.laa.2015.10.018; arXiv: 1505.03373.


  1. Bojan Mohar, Behruz Tayfeh-Rezaie, Median eigenvalues of bipartite graphs, J. Alg. Combin. 41 (2015) 899-909. [Online access][arXiv]
  2. Bojan Mohar, Median eigenvalues and the HOMO-LUMO index of graphs, J. Combin. Theory, Ser. B (2015) 78-92. [Electronic access][arXiv]


  1. Guillaume Chapuy, Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide, Packing triangles in weighted graphs, SIAM J. Discrete Math. 28-1 (2014) 226-239. [Electronic access][arXiv]
  2. Matt DeVos, Zdenek Dvorak, Jacob Fox, Jessica McDonald, Bojan Mohar, and Diego Scheide, A minimum degree condition forcing complete graph immersion, Combinatorica 34 (2014) 279-298. [Electronic access][arXiv]
  3. Azhvan Ahmady, Jason P. Bell, Bojan Mohar, Integral Cayley graphs and groups, SIAM J. Discrete Math. 28 (2014) 685-701. [Online access][arXiv]
  4. Krystal Guo, Bojan Mohar, Large regular bipartite graphs with median eigenvalue 1, Linear Algebra Appl. 449 (2014) 68-75. [Online access][arXiv]
  5. Bojan Mohar, The genus distribution of doubly hexagonal chains, in "Topics in Chemical Graph Theory", I. Gutman, Ed., Mathematical Chemistry Monographs Vol. 16a, Univ. Kragujevac, Kragujevac, 2014, pp. 205-214. [arXiv]
  6. Bojan Mohar, Petr Skoda, Obstructions of connectivity two for embedding graphs into the torus, Canad. J. Math. 66 (2014) 1327-1357. [Online access][arXiv]
  7. Roi Krakovski, Bojan Mohar, Homological face-width condition forcing K6-minors in graphs on surfaces, SIAM J. Discrete Math. 28 (2014) 1257-1275. [Online access][arXiv]


  1. B. Mohar, The excluded minor structure theorem with planarly embedded wall, Ars Math. Contemp. 6 (2013) 187-196. [Electronic access][arXiv]
  2. Matt DeVos, Roi Krakovski, Bojan Mohar, Azhvan Sheikh Ahmady, Integral Cayley multigraphs over Abelian and Hamiltonian groups, Electr. J. Combin. 20(2) (2013), #P63. [Electronic access][arXiv]
  3. Bojan Mohar, Median eigenvalues of bipartite planar graphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 79-84. [Online access]
  4. Bojan Mohar, Many large eigenvalues in sparse graphs, Eur. J. Combin. 34 (2013) 1125-1129. [Electronic access]
    Corrigendum to the paper "Many large eigenvalues in sparse graphs" [European J. Combin. 34 (2013) 1125-1129], Eur. J. Combin. (2015) 141-143. [Electronic access]
  5. Vladimir P. Korzhik, Bojan Mohar, Minimal obstructions for 1-immersions and hardness of 1-planarity testing, J. Graph Theory 72 (2013) 30-71. [Electronic access][arXiv]
  6. Zdenek Dvorak, Bojan Mohar, Robert Samal, Star chromatic index, J. Graph Theory 72 (2013) 313-326. [Electronic access][arXiv]
  7. Zdenvek Dvorak, Bojan Mohar, Chromatic number and complete graph substructures for degree sequences, Combinatorica 33 (2013) 513-529. [Online access][arXiv]
  8. Bojan Mohar, Gabor Simonyi, Gabor Tardos, Local chromatic number of quadrangulations of surfaces, Combinatorica 33 (2013) 467-494. [Online access][arXiv]
  9. Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide, A note on forbidding clique immersions, Electr. J. Combin. 20(3) (2013), #P55. [Online access][arXiv]
  10. Sergio Cabello, Bojan Mohar, Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM J. Comput. 42 (2013) 1803-1829. [Online access][arXiv]
  11. Peter Keevash, Zhentao Li, Bojan Mohar, and Bruce Reed, Digraph girth via chromatic number, Siam J. Discrete Math. 27 (2013) 693-696. [Online access]
  12. Bojan Mohar, Tamon Stephen, Expected crossing numbers, in Discrete Geometry and Optimization, K. Bezdek, A. Deza, and Y. Ye (eds.), Fields Institute Communications, Vol. 69, Springer, 2013, pp. 191-211. [Online access][arXiv]


  1. B. Mohar, S. Spacapan, Degenerate and star colorings of graphs on surfaces, Europ. J. Combin. 33 (2012) 340-349. [Electronic access]
  2. Bojan Mohar, Azhvan Sheikh Ahmady, Rayman Preet Singh, Eigenvalues of graphs with vertices of large degree at distance three apart, Linear Algebra Appl. 436 (2012) 4342-4347. [Electronic access]
  3. Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide, Immersing complete digraphs, Europ. J. Combin. 33 (2012) 1294-1302. [Electronic access][arXiv]
  4. Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar, Linkless and flat embeddings in 3-space, Discrete Comput. Geom. 47 (2012) 731-755. [Electronic access]
  5. Ararat Harutyunyan, Bojan Mohar, Two results on the digraph chromatic number, Discrete Math. 312 (2012) 1823-1826. [Electronic access][arXiv]
  6. Ararat Harutyunyan, P. Mark Kayll, Bojan Mohar, Liam Rafferty, Uniquely D-colourable digraphs with large girth, Canad. J. Math. 64 (2012) 1310-1328. [Electronic access][arXiv]
  7. Ararat Harutyunyan, Bojan Mohar, Planar graphs have exponentially many 3-arboricities, SIAM J. Discrete Math. 26 (2012) 1269-1280. [Electronic access][arXiv]
  8. Z. Dvorak, B. Mohar, Spectrally degenerate graphs: Hereditary case, J. Combin. Theory, Ser. B 102 (2012) 1099-1109. [Electronic access][arXiv]
  9. Roi Krakovski, Bojan Mohar, Spectrum of Cayley graphs on the symmetric group generated by transpositions, Linear Algebra Appl. 437 (2012) 1033-1039. [Electronic access][arXiv]
  10. Daniel Kral', Bojan Mohar, Atsuhiro Nakamoto, Ondrej Pongrac, Yusuke Suzuki, Coloring Eulerian triangulations of the Klein bottle, Graphs Combin. 28 (2012) 499-530. [Electronic access]
  11. Bojan Mohar, Petr Skoda, Minimizing the number of label transitions around a nonseparating vertex of a planar graph, J. Graph Algorithms and Applications 16 (2012) 225-241. [Electronic access][Journal]
  12. Jessica McDonald, Bojan Mohar, Diego Scheide, Kempe equivalence of edge-colourings in subcubic and subquartic graphs, J. Graph Theory 70 (2012) 226-239. [Electronic access][arXiv]


  1. G. Chapuy, E. Fusy, O. Gimenez, B. Mohar, M. Noy, Asymptotic enumeration and limit laws for graphs of fixed genus, J. Combin. Theory, Ser. A 118 (2011) 748-777. [Online access][arXiv]
  2. B. Mohar, A. Vodopivec, The genus of Petersen powers, J. Graph Theory 67 (2011) 1-8. [Online access]
  3. Ararat Harutyunyan, Bojan Mohar, Gallai's theorem for list coloring of digraphs, SIAM J. Discrete Math. 25 (2011) 170-180. [Online access]
  4. S. Cabello, B. Mohar, Crossing number and weighted crossing number of near-planar graphs, Algorithmica 60 (2011) 484-504. [Electronic access][PDF file]
  5. Guantao Chen, Yoshimi Egawa, Ken-ichi Kawarabayashi, Bojan Mohar, and Katsuhiro Ota, Toughness of Ka,t-minor-free graphs, Electr. J. Combin. 18 (2011) #P148, 6 pages. [Free online access]
  6. Matt DeVos, Bojan Mohar, Robert Samal, Unexpected behaviour of crossing sequences, J. Combin. Theory, Ser. B 101 (2011) 448-463.[Electronic access][PDF file][arXiv]
  7. Ararat Harutyunyan, Bojan Mohar, Strengthened Brooks' Theorem for digraphs of girth at least three, Electr. J. Combin. 18 (2011), P195, 11 pages.[Electronic access]
  8. Bojan Mohar, Petr Skoda, On minimizing the number of label transitions around a vertex of a planar graph, in "Combinatorial Algorithms", C.S. Iliopoulos and W.F. Smyth (Eds.), IWOCA 2011, Lecture Notes in Computer Science 7056, Springer-Verlag, 2011, pp. 300-309. [Electronic access]


  1. K.-I. Kawarabayashi, B. Mohar, Star colorings and acyclic colorings of locally planar graphs, SIAM J. Discrete Math. 24 (2010) 56-71.[Electronic access][PDF file]
  2. B. Mohar, I. Rivin, Simplices and spectra of graphs, Discrete Comput.Geom. 43 (2010) 516-521.[Electronic access][PDF file]
  3. B. Mohar, Eigenvalues and colorings of digraphs, Linear Algebra Appl.432 (2010) 2273-2277.[Electronic access][PDF file]
  4. Z. Dvorak, B. Mohar, Crossing-critical graphs with large maximum degree, J. Combin. Theory, Ser. B 100 (2010) 413--417.[Electronic access][PDF file]
  5. A. Vodopivec, F. H. Kaatz, B. Mohar, Topographical distance matrices for porous arrays, J. Math. Chem. 47 (2010), 1145--1153.[Electronic access][PDF file]. Erratum, J. Math. Chem. 47 (2010), 1483.[Electronic access]
  6. Bojan Mohar, Jesus Salas, On the non-ergodicity of the Swendsen-Wang-Kotecky algorithm on the kagome lattice, J. Stat. Mech.: Theory and Experiment (2010) P05016.[Electronic access][PDF file][arXiv]
  7. S. Cabello, B. Mohar, Adding one edge to planar graphs makes crossing number hard, in Proceedings of the 2010 Annual Symposium on Computational Geometry (Snowbird, Utah, USA, June 13-16, 2010), SoCG'10, ACM, New York, pp. 68-76.[Electronic access][PDF file]
  8. K. Kawarabayashi, S. Kreutzer, B. Mohar, Linkless and flat embeddings in 3-space in quadratic time, in Proceedings of the 2010 Annual Symposium on Computational Geometry (Snowbird, Utah, USA, June 13-16, 2010), SoCG'10, ACM, New York, pp. 97-106. [Electronic access][PDF file]
  9. B. Mohar, Strong embeddings of minimum genus, Discrete Math. 310 (2010) 2595-2599. [Electronic access][PDF file][arXiv]
  10. S. Cabello, M. DeVos, J. Erickson, B. Mohar, Finding one tight cycle, ACM Trans. Algorithms 6 (2010) 1-13. [Electronic access][PDF file]
  11. G. Fijavz, B. Mohar, Rigidity and separation indices of graphs in surfaces, Graphs Combin. 26 (2010) 491-498. [Electronic access][PDF file]
  12. Matt DeVos, Agelos Georgakopoulos, Bojan Mohar, Robert Samal, An Eberhard-like theorem for pentagons and heptagons, Discrete Comput. Geom. 44 (2010) 931-945. [Electronic access][PDF file][arXiv]
  13. M. DeVos, K. Kawarabayashi, B. Mohar, H. Okamura, Immersing small complete graphs, Ars Math. Contemp. 3 (2010) 139-146. [Free online access][PDF file]
  14. B. Mohar, A strengthening and a multipartite generalization of the Alon-Boppana-Serre Theorem, Proc. Amer. Math. Soc. 138 (2010) 3899-3909. [Online access][arXiv]
  15. Z. Dvorak, B. Mohar, Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, J. Combin. Theory Ser. B 100 (2010) 729-739. [Online access][PDF file][arXiv]
  16. Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar, Approximation algorithms via contraction decomposition, Combinatorica 30 (2010) 533-552. [Online access][PDF file]
  17. B. Mohar, 2-cell embeddings with prescribed face lengths and genus, Ann. Combin. 14 (2010) 525-532. [Online access][PDF file]

For the most recent preprints please contact Bojan Mohar by email.
Revised: October 26, 2015.