I am interested in structural and extremal graph theory and graph algorithms.


Roughly speaking, I work on problems related to graph containments, such as the subgraph containment, induced subgraph containment, minor containment, topological minor containment and immersion containment. More precisely, I am interested in (but not limited to) the following specific topics.


l         Structure theorems and its applications to algorithms:
Structure theorems describe the structure information of the graphs that do/do not contain certain substructure or do/do not have certain property. Such theorems are the cornerstone of difficult theorems such as the Graph Minor Theorem and the Strong Perfect Graph Theorem. They also lead to numerous algorithmic applications such as developing approximation algorithms and fixed-parameter tractable algorithms.

l         Graph parameters:
Studying graph parameters, such as chromatic number, matching number, feedback vertex number and domination number etc, is one of the most popular directions in graph theory and combinatorial optimization. Many graph parameters are the optimal values of integer programming problems, but computing the exact value of those parameters is usually theoretically difficult. One approach is to study extremal problems which ask for the upper bound or lower bound of those parameters. Another approach is to study algorithmic problems which ask for efficient algorithms for computing the exact value or approximating those parameters. When considering these two approaches, questions are interesting only if certain graph structures were forbidden with respect to various kinds of graph containments. Some other approaches related to the duality theorem, such as the Erdos-Posa type theory and fractional graph theory are also considered.

l         Density and sparsity:
Intuitively, graphs with many edges are dense so that they contain certain substructures; conversely, graphs with few edges are sparse so that they enjoy certain properties. Studying the bounds for the density and sparsity that force the existence of the substructure or the satisfaction of certain property is a central topic in extremal graph theory.