Professor Wenan Zang

Professor Zang's research interests encompass combinatorics and optimization; his recent works are primarily related to integral polyhedra, min-max relations, algorithm design, computational complexity, and good characterizations. By using polyhedral, linear programming, and structure-driven approaches, he has successfully resolved several important long-standing open problems in his research fields, such as the three-color conjecture (which is a counterpart of the celebrated Four-Color Theorem) made by Toft in 1974, the conjecture on recognizing TDI systems proposed by Edmonds and Giles in 1984, the conjecture on maximal cliques and stable sets formulated by Chvátal in 1992, two conjectures on graph circumferences suggested by Seymour and Thomas in 1992, the conjecture on critical partial Latin squares made by Cameron and Keedwell in 1993, the problem on perfect graphs proposed by Hsu and Nemhauser in 1984, the problem related to the traveling salesman polyhedron raised by Cornuéjols, Fonlupt and Naddef in 1985, and the problem of recognizing box-TDI systems posed by Schrijver in 1986. Through a series of papers he has also significantly advanced the theory of polyhedral combinatorics, which plays a central role in operations research and theoretical computer science. Moreover, he has discovered (jointly with his collaborators) some powerful and novel combinatorial methods for tackling various important optimization problems.

PUBLICATIONS

(with Q. Chen and X. Chen) A Polyhedral Description of Kernels, Math. Oper. Res., to appear.
(with Z. Chen and J. Ma) Coloring Digraphs with Forbidden Cycles, J. Combin. Theory Ser. B, to appear.
(with Y. Wu, D. Ye, and C.Q. Zhang) Nowhere-Zero 3-Flows in Signed Graphs, SIAM J. Discrete Math. 28 (2014), 1828-1637.
(with Z. Hu and K. Law) An Optimal Binding Number Condition for Bipancyclism, SIAM J. Discrete Math. 27 (2013), 597-618.
(with J. Ma and X. Yu) Approximate Min-Max Relations on Plane Graphs, J. Comb. Optim. 26 (2013), 127-134.
(with G. Chen and X. Yu) The Circumference of a Graph with no K_3,t-Minor, II, J. Combin. Theory Ser. B 102 (2012), 1211-1240.
(with X. Chen, G. Ding, and X. Hu) The Maximum-Weight Stable Matching Problem: Duality and Efficiency, SIAM J. Discrete Math. 26 (2012), 1346-1360.
(with X. Chen and Z. Chen) Total Dual Integrality in Some Facility Location Problems, SIAM J. Discrete Math. 26 (2012), 1022-1030.
(with X. Chen, G. Ding, and X. Yu) Bonds with Parity Constraints, J. Combin. Theory Ser. B 102 (2012), 588-609.
(with G. Chen and X. Yu) Approximating the Chromatic Index of Multigraphs, J. Comb. Optim. 21 (2011), 219-246.
(with X. Chen and Z. Chen) A Unified Approach to Box-Mengerian Hypergraphs, Math. Oper. Res. 35 (2010), 655-668.
(with G. Ding) Packing Circuits in Matroids, Math. Program. Ser. A 119 (2009), 137-168.
(with Y. Wu and C.Q. Zang) A Characterization of Almost CIS Graphs, SIAM J. Discrete Math. 23 (2009), 749-753.
(with X. Chen and G. Ding) The Box-TDI System Associated with 2-Edge Connected Spanning Subgraphs, Discrete Applied Math. 157 (2009), 118-125.
(with Z. Chen) Odd K₄'s in Stability Critical Graphs, Discrete Math. 309 (2009), 5982-5985.
(with X. Chen and G. Ding) A Characterization of Box-Mengerian Matroid Ports, Math. Oper. Res. 33 (2008), 497-512.
(with G. Ding and L. Feng) The Complexity of Recognizing Linear Systems with Certain Integrality Properties, Math. Program. Ser. A 114 (2008), 321-334.
(with R. Luo, R. Xu, and C.Q. Zhang) Realizing Degree Sequences with Graphs Having Nowhere-Zero 3-Flows, SIAM J. Discrete Math. 22 (2008), 500-519.
(with X. Chen and X. Hu) A Min-Max Theorem on Tournaments, SIAM J. Comput. 37 (2007), 923-937.
(with X. Chen, G. Ding, and X. Hu) A Min-Max Relation on Packing Feedback Vertex Sets, Math. Oper. Res. 31 (2006), 777-788.
(with G. Chen, L. Sheppardson, and X. Yu) The Circumference of a Graph with no K_3,t-Minor, J. Combin. Theory Ser. B 96 (2006), 822-845.
(with G. Chen, Z. Gao, and X. Yu) Approximating Longest Cycles in Graphs with Bounded Degrees, SIAM J. Comput. 36 (2006), 635-656.
(with Y. Li) Differential Methods for Finding Independent Sets in Hypergraphs, SIAM J. Discrete Math. 20 (2006), 96-104.
(with X. Chen) An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs, Algorithmica 44 (2006), 195-211.
(with R. Thomas and X. Yu) Hamilton Paths in Toroidal Graphs, J. Combin. Theory Ser. B 94 (2005), 214-236.
(with X. Li) A Combinatorial Algorithm for Minimum Weighted Colorings of Claw-Free Perfect Graphs, J. Comb. Optim. 9 (2005), 331-347.
(with X. Chen and Z. Hu) Perfect Circular Arc Coloring, J. Comb. Optim. 9 (2005), 267-280.
(with Y. Li and X. Tang) Ramsey Functions Involving K_m,n with n Large, Discrete Math. 300 (2005), 120-128.
(with R. Luo and C.Q. Zhang) Nowhere-Zero 4-Flows, Simultaneous Edge-Colorings, and Critical Partial Latin Squares, Combinatorica 24 (2004), 641-657.
(with X. Deng and G. Li) Proof of Chvátal's Conjecture on Maximal Stable Sets and Maximal Cliques in Graphs, J. Combin. Theory Ser. B 91 (2004), 301-325.
(with B. Chen and X. Deng) On-line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time, J. Comb. Optim. 8 (2004), 85-95.
(with G. Liu) f-Factors in Bipartite (mf)-Graphs, Discrete Applied Math. 136 (2004), 45-54.
(with X. Deng, G. Li, and Y. Zhou) A 2-Approximation Algorithm for Path Coloring on a Restricted Class of Trees of Rings, J. Algorithms 47 (2003), 1-13.
(with Y. Li) The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers, J. Comb. Optim. 7 (2003), 353-359.
(with Y. Li) Ramsey Numbers Involving Large Dense Graphs and Bipartite Turán Numbers, J. Combin. Theory Ser. B 87 (2003), 280-288.
(with G. Ding and Z. Xu) Packing Cycles in Graphs, II, J. Combin. Theory Ser. B 87 (2003), 244-253.
(with G. Ding) Packing Cycles in Graphs, J. Combin. Theory Ser. B 86 (2002), 381-407.
(with M. Cai and X. Deng) A Min-Max Theorem on Feedback Vertex Sets, Math. Oper. Res. 27 (2002), 361-371.
(with F.K. Hwang) Group Testing and Fault Detection for Replicated Files, Discrete Applied Math. 116 (2002), 231-242.
(with M. Cai and X. Deng) An Approximation Algorithm for Feedback Vertex Sets in Tournaments, SIAM J. Comput. 30 (2001), 1993-2007.
(with Y. Li and C. Rousseau) Asymptotic Upper Bounds for Ramsey Functions, Graphs Combin. 17 (2001), 123-128.
(with X. Deng, T. Ibaraki, and H. Nagamochi) Totally Balanced Combinatorial Optimization Games, Math. Program. Ser. A 87 (2000), 441-452.
(with X. Deng and G. Li) Wavelength Allocation on Trees of Rings, Networks 35 (2000), 248-252.
(with M. Cai and X. Deng) Solution to a Problem on Degree Sequences of Graphs, Discrete Math. 219 (2000), 253-257.
Acyclic Digraphs with the Gallai-Milgram-Linial Property for Clique Covers, Discrete Math. 199 (1999), 183-192.
(with M. Cai and X. Deng) A TDI System and Its Application to Approximation Algorithms, Proc. 39^th IEEE Symposium on Foundations of Computer Science (FOCS), Palo Alto, CA, 1998, pp. 227-233.
Coloring Graphs with no Odd K₄, Discrete Math. 184 (1998), 205-212.
Proof of Toft's Conjecture: Every Graph Containing no Fully Odd K₄ is 3-Colorable, J. Comb. Optim. 2 (1998), 117-188. (Invited paper)
(with F.K. Hwang) Detecting Corrupted Pages in M Replicated Large Files, IEEE Trans. Parallel Distrib. Syst. 8 (1997), 1241-1245.
Generalizations of Grillet's Theorem on Maximal Stable Sets and Maximal Cliques in Graphs, Discrete Math. 143 (1995), 259-268.
(with F. Tian) The Maximum Number of Diagonals of a Cycle in a Block and Its Extremal Graphs, Discrete Math. 89 (1991), 51-63.

RESEARCH GRANTS

RGC General Research Fund: Structure-Driven Approaches to Some Network Flow Problems. Date of award: July 1, 2013. Award amount: HK$868,303. (Principal investigator)
RGC General Research Fund: Box-Perfectness: Obstruction and Recognition. Date of award: July 1, 2011. Award amount: HK$849,480. (Principal investigator)
RGC General Research Fund: Optimal Packing and Covering. Date of award: July 1, 2009. Award amount: HK$520,000. (Principal investigator)
Overseas and Hong Kong, Macau Young Scholars Collaborative Research Fund of the National Science Foundation of China: Packing-Covering Dualities and Applications. Date of award: August 30, 2009. Award amount: RMB200,000. (Principal investigator)
RGC General Research Fund: Characterizations of Combinatorial Structures. Date of award: July 1, 2007. Award amount: HK$445,000. (Principal investigator)
RGC General Research Fund: Min-Max Relations and Integral Polyhedra. Date of award: July 1, 2006. Award amount: HK$250,000. (Principal investigator)
RGC General Research Fund: Combinatorial Optimization Problems Involving Cycles. Date of award: July 1, 2005. Award amount: HK$463,600. (Principal investigator)
RGC General Research Fund: Bonds, Cycles, and Ring Networks. Date of award: July 1, 2004. Award amount: HK$318,000. (Principal investigator)
RGC General Research Fund: Optimization: Integrality and Duality. Date of award: July 3, 2003. Award amount: HK$300,000. (Principal investigator)
RGC General Research Fund: Obstructions to Some Combinatorial Properties. Date of award: July 3, 2001. Award amount: HK$327,401. (Principal investigator)
RGC General Research Fund: Algorithms for Some Packing and Covering Problems. Date of award: July 5, 1999. Award amount: HK$405,000. (Principal investigator)
RGC General Research Fund: Graph Coloring: Theory, Algorithms, and Applications. Date of award: July 1, 1997. Award amount: HK$396,000. (Principal investigator)

EDITORIAL BOARDS

Discrete Applied Mathematics, Elsevier, Netherlands, September 2010 - Present.
Operations Research, INFORMS, USA, July 2009 - Present.
Journal of Combinatorial Optimization, Springer, Netherlands, January 2008 - Present.
Acta Mathematicae Applicatae Sinica, Springer, Germany, January 2007 - Present.
Discrete Mathematics, Algorithms, and Applications, World Scientific, USA, January 2009 - Present.

AWARDS AND HONORS

Faculty Knowledge Exchange Award (as a team member), University of Hong Kong, 2012.
Outstanding Researcher Award, University of Hong Kong, 2011.
Research Output Prize, University of Hong Kong, 2011.
Outstanding Research Achievement, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, 2010.
Overseas and Hong Kong, Macau Young Scholars Collaborative Research Fund, National Science Foundation of China, 2009. (This award was previously known as "Overseas Outstanding Young Scholar Award", but the title has been changed to the present one.)
Presentation of one paper by András Sebö, a world-leading expert on operations research, at the Bellairs Workshop on Integer Programming, with title "Recognizing Totally Dual Integral Systems is Hard" (the main theorem of this paper) and subtitle "On Ding, Feng and Zang's Proof and Some Remaining Problems", 2008.
The Best Paper Prize, International Computing and Combinatorics Conference, 2005.
Inclusion of one paper in the very first volume of Discrete Mathematics - Editors' Choice, 1999.
Outstanding Research Fellowship, President of the Chinese Academy of Sciences, 1989.
Outstanding Graduate Award, National University of Defense Technology, 1986.

PLENARY AND INVITED LECTURES

Atlanta Lecture Series in Combinatorics and Graph Theory, Atlanta, USA, April, 2014. (Invited speaker, with airfare and accommodation expense paid by the conference organizers.)
Fields Institute-Ottawa-Carleton Discrete Mathematics Days, Ottawa, Canada, May, 2013. (Plenary speaker, with airfare and accommodation expense paid by Fields Institute.)
International Conference on Cycles in Graphs, Nashville, TN, USA, May, 2012.
Workshop on Combinatorics and Graph Theory, Hunan, China, June, 2012. (Plenary speaker)
The Fourth International Symposium on Graph Theory and Combinatorial Algorithms (GTCA'2011), Beijing, China, July, 2011.
Atlanta Lecture Series in Combinatorics and Graph Theory, Atlanta, USA, February, 2011. (Invited speaker, with airfare and accommodation expense paid by the conference organizers.)
The Fourth National Conference on Combinatorics and Graph Theory, Xuzhou China, August, 2010. (Plenary speaker)
The Third International Symposium on Graph Theory and Combinatorial Algorithms (GTCA'2010), Beijing, China, July, 2010.
The 23rd Cumberland Conference on Combinatorics, Graph Theory, and Computing, Mississippi, USA, May, 2010. (Plenary speaker, with airfare and accommodation expense paid by the conference organizers.)
2009 International and Fifth Cross-strait Conference on Graph Theory and Combinatorics, Tianjin, China, July, 2009.
Canadian Mathematical Society Winter 2008 Meeting, Ottawa, Canada, December, 2008.
Foundations of Computational Mathematics (FoCM'08), Hong Kong, China, June, 2008.
The 46th Midwestern Conference on Graph Theory (MIGHTY-46), West Virginia, USA, April, 2008. (Plenary speaker, with airfare and accommodation expense paid by the conference organizers.)
The 32nd SIAM Southeastern-Atlantic Section Conference (SIAM-SEAS 2008), Orlando, USA, March, 2008.
Fields Institute-Ottawa-Carleton Discrete Mathematics Workshop, Ottawa, Canada, May, 2007. (Plenary speaker, with airfare and accommodation expense paid by Fields Institute.)
International Symposium on Graph Theory and Combinatorial Algorithms (GTCA), Beijing, China, July, 2007.
Workshop on Optimization in Honor of Professor M.J.D. Powell's 70th Birthday, Hong Kong, China, February, 2007.
INFORMS International, Hong Kong, China, June, 2006
The Second National Conference on Combinatorics and Graph Theory, Tianjin, China, August, 2006.
International Workshop on Combinatorial Algorithms and Optimization, Shandong, China, August, 2006. (Plenary speaker)
The Third Pacific Rim Conference on Mathematics, Shanghai, China, August, 2005.
International Conference on Graph Structure Theory, Wuhan, China, July, 2005. (Plenary speaker)
The First National Conference on Combinatorics and Graph Theory, Xinjiang, China, 2004.
Satellite Conference on Combinatorics, International Congress of Mathematicians, Hong Kong, China, 2002.
INFORMS International, Hawaii, USA, June, 2001.
Annual Meeting of Hong Kong Mathematical Society, Hong Kong, China, 2001.
International Conference on Graph Theory, Nanjing, China, 2000. (Plenary speaker)
The First American Mathematical Society (AMS) - Hong Kong Mathematical Society Joint Conference, Hong Kong, China, 2000.

POSTGRADUATE STUDENTS

Chen, Cheng, Ph.D., ongoing.
Tan, Lei, Ph.D., ongoing.
Xiao, Han, Ph.D., ongoing.
Zhao, Qiulan, Ph.D., ongoing.
Sang, Jiajun, Ph.D., ongoing.
Chen, Qin, Ph.D., 2011.
Law, Ka Ho, Ph.D., 2010.
Chen, Zhibin, Ph.D., 2009.
Feng, Li, M.Phil., 2007.
Li, Ching Man, M.Phil., 2007.
Chung, Yau-Lin, M.Phil., 2004.
Lam, Yan-Yan, M.Phil., 2004.
Hui, Ming-Ki, M.Phil., 2002.
Li, Yin Chiu, M.Phil., 2002.
Xu, Zhenzhen, M.Phil., 2002.
Chu, Chi-Kwan, M.Phil., 2000.
Leung, Pak Kin, M.Phil., 1998.