Jing Huang

Dr. Huang's research area is in graph theory. He is particularly interested in the study of graph structures and the uses of structural properties of graphs for solving computational problems. Research results on nicely structured hereditary graph classes (e.g., interval graphs, chordal graphs, comparability graphs, and circular arc graphs, etc.) often capture his attention. Working toward good characterizations (in the sense of Tutte and beyond) of various classes of graphs in terms of vertex orderings, edge orientations, forbidden structures, and geometric representations describes his frequent research activities.

The highlights of Dr. Huang's research include the discovery of the lexicographic method. This method has later been used for finding acyclic local tournament orientations of proper interval graphs, local transitive tournament orientations of proper circular arc graphs, special orientations of two-clique proper circular arc graphs, and transitive orientations of comparability graphs. These orientations are very useful in the design of efficient algorithms in obtaining vertex orderings and geometric representations and solving computational problems of the corresponding graphs.

In a joint work with Feder and Hell, he obtained a dichotomy theorem which classifies the complexity of list homomorphism problems. Solving a longstanding problem, Dr. Huang has obtained several representation characterizations of chordal bigraphs. Most recently, in a joint work with Bang-Jensen and Zhu, he initiated the study of orientation completion problems which generalize many recognition problems as well as representation problems, particularly for those graphs which can be defined in terms of the existence of certain orientations.

Interests

• Graph Theory
• Algorithms
• Complexity

Courses

• Fall 2024: MATH 222: Discrete and Combinatorial Mathematics 
• Spring 2025: MATH 322: Combinatorial Designs  MATH 424: Structural Graph Theory 
• Summer 2025:

Selected Publications

• J. Bang-Jensen, J. Huang, and X. Zhu, Completing orientations of partially oriented graphs, submitted.
• D. Epple and J. Huang, A Brooks-type theorem for the bichromatic number, Journal of Graph Theory 80 (2015) 277 - 286.
• J. Bang-Jensen and J. Huang, Arc-disjoint in- and out-branchings with the same root in locally semicomplete digraphs, Journal of Graph Theory 77 (2014) 278 - 298.
• R. Churchley and J. Huang, On the polarity and monopolarity of graphs, Journal of Graph Theory 76 (2014) 138 - 148.
• J. Bang-Jensen and J. Huang, Decomposing locally semicomplete digraphs into strong spanning subdigraphs, Journal of Combinatorial Theory B 102 (2012) 701 - 714.
• R. Brewster, T. Feder, P. Hell, J. Huang, and G. MacGillivray, Near-unanimity functions and varieties of graphs, SIAM Journal on Discrete Mathematics 22 (2008) 938 - 960.
• J. Huang, Representation characterizations of chordal bipartite graphs, Journal of Combinatorial Theory B 96 (2006) 673 - 683.
• T. Feder, P. Hell, and J. Huang, List homomorphisms and circular arc graphs, Combinatorica 19 (1999) 487 - 505.
• X. Deng, P. Hell, and J. Huang, Linear time representation algorithms for proper circular arc graphs and proper interval graphs, SIAM Journal on Computing 25 (1996) 390 - 403.
• J. Huang, On the structure of local tournaments, Journal of Combinatorial Theory B 63 (1995) 200 - 221.