Skip to content Skip to navigation


Baogang Xu Professor

Research Interests: 
  • Graph Theory
  • Combinatorial Optimization

Educational Background

  • PhD, Operations Research and Cybernetics, Shandong University (1997)
  • MA, Operations Research and Cybernetics, Shandong University (1988)
  • BA, Computational Mathematics, Shandong University (1985)




Research Grants

  1. National Natural Science Foundation of China. Project: On χ-bounded conjecture and related problems, (No. 11571180, Jan. 2016--Dec. 2019, Principal Investigator)
  2. Key project of National Natural Science Foundation of China. Project: Discrete Methods in Network Design, (No. 11331003, Jan. 2014--Dec. 2018, Co-principal Investigator)
  3. Doctoral Fund of Ministry of Education of China. Project: On maximum bipartite subgraphs of triangle-free graphs, (No. 20113207110003, Jan. 2012--Dec. 2014,  Principal Investigator)
  4. National Natural Science Foundation of China. Project: On a conjecture of Thomassen concerning vertex partitions of graphs, (No. 11171160, Jan. 2012--Dec. 2015, Principal Investigator)
  5. Key project of National Natural Science Foundation of China. Project: Extremal Graph Theory, (No. 10931003, Jan. 2010--Dec. 2013, Co-principal Investigator)
  6. National Natural Science Foundation of China. Project: Circular coloring, circular-perfect graphs and related problems, (No. 10671095, Jan. 2007--Dec. 2009, Principal Investigator)
  7. National Natural Science Foundation of China. Project: Colorings, homomorphisms and cycle structures of graphs, (No. 10371055, Jan. 2004--Dec. 2006, Principal Investigator)
  8. Start-up grant of Nanjing Normal University. Project: Restricted Steiner tree problem, (May 2002--Jun. 2004, Principal Investigator)
  9. National Natural Science Foundation of China. Project: Colorings of graphs (No. 10001035, January 2001 -- December 2003, Principal Investigator)
  10. WKC Education Foundation of Chinese Academy of Sciences, Project: List colorings of plane graphs (September 1998 -- May 2000, Principal Investigator)
  11. National Postdoctoral Foundation of China, Project: Colorings of plane graphs (June 1998 -- May 2000, Principal Investigator)


Journal Articles

  1. On judicious partitions of graphs  (with M. Liu), J. Comb. Optim. 31 (2016)1383-1398.
  2. Bipartition of graphs under degree constrains (with M. Liu), Science China Math. 58} (4)(2015)869--874.
  3. The semidefinite programming based approximation algorithms for Max Hypergraph Cut with limited unbalanced (with X. Yu, X. Zhang and Z. Zhang), Science China Math. 57 (2014) 2437--2462.
  4. Forbiden subgraphs and 3-colorings (with Fan, Ye and Yu),  Siam J. Disc. Math. 28 (2014) 1226--1256.
  5. On judicious bisections of graphs (with Yu), J. Combin. Theory B 106 (2014) 30--69.
  6. On minimum balanced bipartitions of triangle-free graphs (with H. Li, Y. Liang and M. Liu),  J. Combinatorial Optimization 27 (2014) 557--566.
  7. Acyclic edge coloring of planar graphs without adjacent cycles (with M. Wan),  Science China Math. 57   (2014) 433-442.
  8. On the complexity of injective colorings and its generalizations (with J.  Jin and X. Zhang),  Theoretical Computer Science 491 (2013) 119-126.
  9. Maximum directed cuts in graphs with degree constraints (with X. Yu),  Graph and Combinatorics 28  (2012) 563--574.
  10. Upper bounds on minimum balanced bipartitions (with G. Fan, X. Yu and C. Zhou),  Disc. Math. 312  (2012) 1077--1083.
  11. Injective choosability of planar graphs of girth five and six (with R. Li), Disc. Math. 312  (2012) 1260--1265.
  12. Better bounds for $k$-partitions of graphs (with X. Yu),  Combin. Probab. and Comp. 20  (2011) 631--640.
  13. Edge choosablity and total choosability of planar graphs with no 3-cycles adjacent 4-cycles (with R. Li),  Discrete Math. 311  (2011) 2158--2163.
  14. Some results on acyclic edge coloring of plane graphs (with W. Dong),  Information Processing Letters 110  (2010) 887--892.
  15. Improved bounds on linear coloring of plane graphs (with W. Dong and X. Zhang),  Science China Mathematics 53  (2010) 1895--1902.
  16. A note on balanced bipartitions (with J. Yan and X. Yu), Discrete Math. 310 (2010) 2613--2617.
  17. Balanced judicious partitions of graphs (with J. Yan and X. Yu),  J. Graph Theory 63  (2010) 210--225.
  18. A forbidden subgraphs characterization of line-polar bipartite graphs (with J. Huang),  Disc. Appl. Math.  158 (2010) 666-680.
  19. Acyclic 5-choosable planar graphs with neither 4-cycles nor chordal 6-cycles (with H. Zhang),  Disc. Math. 309 (2009) 6087--6091.
  20. On a bipartition problem of Bollob\'as and Scott (with X. Yu),  Combinatorica 29 (2009) 595--618.
  21. Judicious k-partitions of graphs (with X. Yu), J. Combin. Theory  Ser. B  99 (2009) 324--337.
  22. A note on list improper coloring of plane graphs (with W. Dong), Disc. Appl. Math. 157 (2009) 433--436.
  23. On (3,1)*-coloring of plane graphs, SIAM J. Disc. Math. 23 (2008) 205--220.
  24. Triangle-free subcubic graphs with minimum bipartite density (with X. Yu), J. of Combin. Theory Ser. B 98 (2008) 516--537.
  25. On minimally circular-imperfect graphs, Disc. Math. 308 (2008) 3134--3142.
  26. A 3-color theorem on plane graphs without 5-circuits,  Acta Mathematica Sinica (English Ser.) 23 (2007) 1059--1062.
  27. An analogue of Dirac's theorem on circular super-critical graphs,  European J. of combinatorics 28 (2007) 1270--1275.
  28. On 3-colorable plane graphs without 5- and 7-cycles, J. of Combin. Theory Ser. B  96 (2006) 958--963.
  29. Optimal relay location for energy constrained wireless ad-hoc networks (with I. Cardei, M. Cardei, L. Wang and D.-Z. Du),J. of Global Optimization 36 (2006) 391--399.
  30. Minimally circular imperfect graphs with a major vertex, Discrete Math. 301 (2005) 239--242.
  31. On 3-colorings of plane graphs, Acta Math. Appl. Sin. 20 (2004)  597--604.  
  32. Two conjectures equivalent to the perfect graph conjecture, Discrete Math. 258 (2002) 347--351.
  33. Hajos' conjecture and projective graphs (with G. Fan), Discrete Math. 252 (2002) 91--101.
  34. On structure of graphs embedded on surfaces of nonnegative characteristic with application to choosability,  Discrete Math. 248 (2002) 283--291.
  35. On structure of some plane graphs with application to choosability (with P.C.B. Lam and W.C. Shiu),  J. of Combin. Theory Ser. B 82 (2001) 285--297.
  36. The 4-choosability of plane graphs without 4-cycles (with Peter C.B. Lam and J. Liu),  J. of Combin. Theory Ser. B  76 (1999) 117--126.
  37. A sufficient condition for bipartite graphs to be of Type one,  J. Graph Theory 29 (1998) 133--137.
  38. On endo-homology of complexes of graphs (with L. Xie and G. Liu), Discrete Math. 188  (1998) 285--291.
  39. On the fixed edges of planar graphs with minimum degree five (with H. Fan),  Discrete Math. 152 (1996) 325--328.


Honors and Awards

  1. Outstanding contributor of “10000 Selected Problems in Sciences”, 2009
  2. Outstanding Teacher of Nanjing Normal University, 2009
  3. Candidate of Academic Leaderships of the “Green-Blue Project”of Jiangsu Province, 2006
  4. WKC Postdoctoral Fellowship of Chinese Academy of Sciences, 1998--1999
  5. Graduate Excellence Award, Shandong University, 1995


Academic Title

  1. Executive member  (2006--),and the Secretary-Genera (2014--),of the council of the Chinese Society of Combinatorics and Graph Theory,.
  2. Executive member (2006.08--), and Vice Chairman (2010.08--2015.07), of the council of  Graph Theory and Combinatorics at the Chinese Society of Operations Research.
  3. Member of the council of the Chinese Society of Operations Research (2012--).



Office phone:+86-25-85891380-8634

Cell phone:, OR

Mail address: School of Mathematical Sciences, Nanjing Normal University,

              1 Wenyuan Road, Nanjing, 210023, China