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.