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. T. Bohme, K.-I. Kawarabayashi, J. Maharry, B. Mohar, K3,k-minors in large 7-connected graphs, submitted to JCTB, May 2008, last revision made in 2018. [PDF file]
  2. Matt DeVos, Bojan Mohar, Small separations in vertex transitive graphs, Forum. Math. sigma, submitted, 2012. [Electronic access][arXiv]
  3. Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar, Bruce Reed, Flat embeddings in 3-space in linear time, submitted. [Electronic access][arXiv]
  4. Bojan Mohar, Petr Skoda, Discharging proofs made easy, submitted. [Electronic access][arXiv]
  5. 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
  6. 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{http://dx.doi.org/10.1137/1.9781611973730.115}
  7. Pavol Hell, Bojan Mohar, Arash Rafiey, Ordering without forbidden patterns, submitted to JGT. arXiv: 1408.1461
  8. Seyed Saeed Changiz Rezaei, Seyyed Aliasghar Hosseini, Bojan Mohar, Cubic normal graphs, submitted, October 2014.
  9. 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, October 2015. arXiv: 1510.00549.
  10. Sergio Cabello, Bojan Mohar, Robert Samal, Drawing a disconnected graph on the torus, Eurocomb 2015.
  11. Ross Churchley, Bojan Mohar, and Hehui Wu, Weak duality for packing edge-disjoint odd (u, v)-trails, SODA 2016; accepted.
  12. Hong-Hai Li, Bojan Mohar, On the first and second eigenvalue of finite and infinite uniform hypergraphs, Proc. AMS, in print.
  13. David Gajser, Bojan Mohar, Minimal normal graph covers, Combinatorica, published online. doi: 10.1007/s00493-017-3559-2, arXiv: 1601.01129
  14. Gary Greaves, Bojan Mohar, and Suil O, Interlacing families and the Hermitian spectral norm of digraphs, submitted, July 2017. arXiv: 1602.06274
  15. Carlos A. Alfaro, Alan Arroyo, Marek Der\v n\'ar, and Bojan Mohar, The crossing number of the cone of a graph, SIAM J. Discrete Math., in print. arXiv: 1608.07680
  16. Zden\v ek Dvo\v r\'ak, Daniel Kr\'al', Bojan Mohar, Graphic TSP in cubic graphs. arXiv: 1608.07568.
  17. Zden\v{e}k Dvo\v r\'ak, Bojan Mohar, and Robert \v S\'amal, Exponentially many nowhere-zero $Z_3$-, $Z_4$-, and $Z_6$-flows, submitted, September 2017.
  18. Seyyed Aliasghar Hosseini, Bojan Mohar, and Mohammad Bagher Ahmadi, The evolution of the structure of ABC-minimal trees, submitted to JCTB, September 2017. arXiv: 1804.02098
  19. Ross Churchley, Bojan Mohar, A submodular measure and approximate Gomory-Hu theorem for packing odd trails, SODA 2018.
  20. Fiachra Knox and Bojan Mohar, Maximum number of colourings: 4-chromatic graphs, submitted to JCTB. arXiv: 1708.01781
  21. Fiachra Knox and Bojan Mohar, Maximum number of colourings: 5-chromatic case, submitted to Electronic J. Combin., May 2018. arXiv: 1710.06535
  22. Anthony Bonato, Bojan Mohar, Topological directions in Cops and Robbers, J. Combinatorics, accepted. arXiv: 1709.09050
  23. Eric Colin de Verdiere, Thomas Magnard, and Bojan Mohar, Embedding graphs into two-dimensional simplicial complexes, SoCG 2018.
  24. Zden\v{e}k Dvo\v r\'ak, Petr Hlineny, and Bojan Mohar, Structure and enumeration of crossing-critical graphs, arXiv: 1803.01931
  25. Yifan Jing, Bojan Mohar, The genus of a random bipartite graph, submitted to Canad. J. Math., April 2018. arXiv: 1712.09989
  26. Haiyan Chen, Bojan Mohar, The sandpile group of a polygon flower, submitted, June 2018.
  27. Yifan Jing, Bojan Mohar, Efficient polynomial-time approximation scheme for the genus of dense graphs, FOCS 2018.
  28. Sergio Cabello, Bojan Mohar, and Hebert P\'erez-Ros\'es, The Inverse Voronoi Problem in graphs, ESA 2018.
  29. Yifan Jing, Bojan Mohar, The genus of complete 3-uniform hypergraphs, submitted to JCTB, May 2018. arXiv: 1805.01557
  30. Matt DeVos, Sebasti\'an Gonz\'alez Hermosillo de la Maza, Krystal Guo, Daryl Funk, Tony Huynh, Bojan Mohar, and Amanda Montejano, Short rainbow cycles in sparse graphs, arXiv: 1806.00825
  31. Fiachra Knox, Bojan Mohar, and David Wood, Exponential golden ratio inequality for vertex degrees of graphs, submitted, AMM, arXiv: 1808.00640
  32. Bojan Mohar, Hehui Wu, Fractional chromatic number of a random subgraph, submitted to Combinatorica, July 2018. arXiv: 1807.06285
  33. Vida Dujmovi\'c, Ken-ichi Kawarabayashi, Bojan Mohar and David R. Wood, Tight upper bounds on the crossing number in a minor-closed class, submitted to DCG, August 2018. arXiv: 1807.11617
  34. Bojan Mohar, Hehui Wu, Triangle-free subgraphs with large fractional chromatic number, submitted to CPC, August 2018. arXiv: 1808.01605

2018

  1. B. Afshari, S. Akbari, M. J. Moghaddamzadeh, and B. Mohar, The algebraic connectivity of a graph and its complement, Linear Algebra Appl. 555 (2018) 157-162. doi: 10.1016/j.laa.2018.06.015; arXiv: 1806.06770
  2. Seyyed Aliasghar Hosseini and Bojan Mohar, Game of cops and robbers in oriented quotients of the integer grid, Discrete Math. 341 (2018) 439-450. doi: 10.1016/j.disc.2017.09.011
  3. M. Kotrbcik, N. Matsumoto, B. Mohar, A. Nakamoto, K. Noguchi, K. Ozeki, and A. Vodopivec, Grunbaum colorings of even triangulations on surfaces, J. Graph Theory 87 (2018) 475-491. doi:10.1002/jgt.22169
  4. Frederic Havet, A. Karolinna Maia, Bojan Mohar, Finding a subdivision of a prescribed digraph of order 4, J. Graph Theory 87 (2018) 536-560. doi: 10.1002/jgt.22174. arXiv: 1708.01777
  5. Bojan Mohar, The structure of ABC-minimal trees with given number of leaves, MATCH Commun. Math. Comput. Chem. 79 (2018) 415-430. arXiv:1706.02891

2017

  1. Fiachra Knox, Sebastian Gonzalez Hermosillo de la Maza, Naoki Matsumoto, Bojan Mohar, and Claudia Linhares Sales, Proper Orientations of Planar Bipartite Graphs, Graphs Combin. 33 (2017) 1189-1194. doi: 10.1007/s00373-017-1836-x; arXiv: 1609.06778
  2. Zhentao Li, Bojan Mohar, Planar digraphs of digirth four are 2-colorable, SIAM J. Discrete Math. 31 (2017) 2201-2205. doi: 10.1137/16M108080X; arXiv: 1606.06114
  3. Seyed Saeed Changiz Rezaei, Seyyed Aliasghar Hosseini, Bojan Mohar, Almost all regular graphs are normal, Discrete Appl. Math. 230 (2017) 51-55. doi: 10.1016/j.dam.2017.07.001; arXiv: 1511.07591.
  4. Bojan Mohar, Bruce Reed, David Wood, Colourings with bounded monochromatic components in graphs of given circumference, Australasian J. Combin. 69(2) (2017) 236-242. arXiv: 1612.05674
  5. Krystal Guo, Bojan Mohar, Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths, Discrete Math. 340 (2017) 2616-2632. doi: 10.1016/j.disc.2017.01.018.
  6. Krystal Guo, Bojan Mohar, Hermitian adjacency matrix of digraphs and mixed graphs, J. Graph Theory 85 (2017) 217-248. doi: 10.1002/jgt.22057; arXiv: 1505.01321.
  7. Ararat Harutyunyan, Bojan Mohar, Planar digraphs of digirth five are 2-colorable, J. Graph Theory 84 (2017) 408-427. doi: 10.1002/jgt.22032; arXiv: 1401.2213
  8. Zdenek Dvorak, Bernard Lidicky, Bojan Mohar, 5-choosability of graphs with crossings far apart, J. Combin. Theory, Ser. B 123 (2017) 54-96. doi: 10.1016/j.jctb.2016.11.004; arXiv: 1201.3014
  9. Zdenek Dvorak, Bernard Lidicky, Bojan Mohar, Luke Postle, 5-list-coloring planar graphs with distant precolored vertices, J. Combin. Theory, Ser. B 122 (2017) 311-352. doi: 10.1016/j.jctb.2016.06.006; arXiv: 1209.0366
  10. Dan Archdeacon, Matt DeVos, Stefan Hannie, and Bojan Mohar, Whitney's theorem for 2-regular planar digraphs, Australasian J. Combinatorics 67(2) (2017) 159-165. http://ajc.maths.uq.edu.au ; arXiv:1706.02914
  11. Dan Archdeacon, C. Paul Bonnington, and Bojan Mohar, Embedding quartic Eulerian digraphs on the plane, Australasian J. Combinatorics 67(2) (2017) 364-377. http://ajc.maths.uq.edu.au ; arXiv:1706.02896
  12. Bojan Mohar, Petr Skoda, Obstructions for two-vertex alternating embeddings of graphs in surfaces, Europ. J. Combin. 59 (2017) 96-113. doi: 10.1016/j.ejc.2016.08.001. arXiv:1112.0800

2016

  1. Bojan Mohar, Hehui Wu, Dichromatic number and fractional chromatic number, Forum of Mathematics, Sigma 4 (2016) e32, 14 pages. doi: 10.1017/fms.2016.28
    arXiv:1510.05982
  2. Bojan Mohar, Median eigenvalues of bipartite subcubic graphs, Combinatorics, Probability and Computing 25 (2016) 768-790. doi: 10.1017/S0963548316000201; arXiv: 1309.7395
  3. Zdenek Dvorak, Bojan Mohar, Crossing numbers of periodic graphs, J. Graph Theory 83 (2016) 34-43. doi: 10.1002/jgt.21912; arXiv: 1405.5117
  4. Bojan Mohar, Arash Rafiey, Behruz Tayfeh-Rezaie, and Hehui Wu, Interval minors of complete bipartite graphs, J. Graph Theory 82 (2016) 312-321. doi: 10.1002/jgt.21903; arXiv: 1408.1155
  5. Bojan Mohar, Hermitian adjacency spectrum and switching equivalence of mixed graphs, Linear Algebra Appl. 489 (2016) 324-340. doi: 10.1016/j.laa.2015.10.018; arXiv: 1505.03373.

2015

  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]
  3. Matt DeVos, Bojan Mohar, Robert Samal, Highly arc-transitive digraphs - Structure and counterexamples, Combinatorica 35 (2015) 553-571. [Online access][arXiv]

2014

  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]

2013

  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]

2012

  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]

2011

  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]

2010

  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: avgust 31, 2018.