“The 4-color theorem has many restatements and generalizations, some of which has motivated the study of my thesis.” Weiqiang Yu, former PhD student at IRIF.
Link to his PhD thesis: Signature packing and vertex partition of signed graphs and graphs

My name is Weiqiang Yu, I obtained my Bachelor's and Master's degrees from Zhejiang Normal University. I did my PhD. at Institut de Recherche en Informatique Fondamentale (IRIF) under the supervision of Reza Naserasr, funded by China Scholarship Council. I mainly work on graph partition, coloring and packing problems of graphs and signed graphs.

During my master degree, I had a course in graph theory given by Douglas B. West, who is a famous graph theorist, and I found the course quite interesting, so I kept working on graph theory. Later I met Reza Naserasr in a conference of graph theory in China, who became my phd. supervisor and help me a lot in my studies and research.

Graph partition is one of the central problem in graph theory, originated from the famous 4-color problem. In my thesis, two major problems concerning graph partition are considered: the edge separation of signed graphs and the vertex decomposition of sparse graphs.

The 4-color theorem, one of the most outstanding discovery in graph theory, was first presented as a question by Francis Guthrie in 1852, who tried to color a map with four colors such that no two adjacent regions have the same color. The problem, which was so simply described but so difficult to prove, caught a lot of attention of many mathematicians at the time. After various attempts during more than one hundred years, a first complete proof, assisted by computer, was achieved by Kenneth Appel and Wolfgang Haken in 1976. However, the proof was infeasible for a human to check by hand. It having been a motivating question for studying graphs, planarity, embedding of graphs, coloring techniques in graph theory.

The 4-color theorem has many restatements and generalizations, some of which has motivated the study of my thesis. One of the most famous equivalent restatement of the 4-color theorem proposed by Tait is that every planar bridgeless cubic graph is 3-edge-colorable. Later Paul Seymour proposed a more general conjecture about the edge coloring of planar graphs, saying that every k-regular planar graph is k-edge colorable if for each set X of odd number of vertices the edge cut (X, V-X) is of size at least k. Another restatement of the 4-color theorem regarding graph decomposition is that a planar graph is 4-colorable if and only if its vertex set can be decomposed into four parts, each part induces an independent set. These further inspired the study of signature packing and vertex decomposition of graphs.

In signature packing of signed graphs, packing number is actually captured by a homomorphism to special signed graphs SPC_d, which is strongly connected to one of the generalisation of 4-color theorem. And the vertex decomposition also generalizes the coloring of graphs.

At the moment, we are still working on several problems related to my thesis. For example, the fractional version of packing, polytopes of signed graph etc. And in the future, I also hope to work on different problems in graph theory.