Travel Report: Shenwei Huang, Computing, United Kingdom
I was honored to receive International Research Travel Award to work with Daniel Paulusma and Matthew Johnson, two professors at School of Engineering and Computing Sciences, Durham University in UK.
During my visit in May 2014, Daniel, Matthew and I continued a project on graph coloring that we already started early this year. A graph is a mathematic notion to model networks in which each object is called a vertex while a link, which we call an edge, may or may not exist between any pairs of objects. The graph coloring problem is to color vertices of a graph in such a way that any two vertices should not be colored alike whenever there is an edge between them. If we are only allowed to use a fixed number of colors, say k colors, then the problem is called k-coloring. In general, k-coloring is NP-complete, which roughly means that it is hard for a computer with the most powerful computational capacity to decide if a given graph can be colored using at most k colors. We studied this problem on ( , ) s t C P -free graphs, those that exclude a path t P and a cycle s C as induced subgraphs. We proved that k-coloring remains NPcomplete on ( , ) s t C P -free graphs for some values of s and t, and give a summary of complexity of k-coloring as well as two generalizations in terms of all combinations of s and t.
Moreover, Daniel and I, together with one of Daniel’s postdocs, Konrad Dabrowski, started a project on clique-width. Clique-width of a graph is the minimum number of labels needed to construct the graph under a set of specific rules. The typical problem one asks in this area is that if a given graph class has bounded or unbounded clique-width. Clique-width is closely related to the existence of efficient algorithms on graphs. The celebrated Courcelle’s Theorem states that any graph property that can be expressed in certain second order logic admits a linear time algorithm on any graph class of bounded clique-width. Therefore, it is vital to find graph classes of bounded clique-width. What we did was to investigate graphs that exclude two small graphs H1 and H2 as induced subgraphs. We refer to these graphs as (H1,H2)-free graphs. Continuing a line of Dabrowski and Paulusma, we found, via a new technique we developed, three more pairs (H1,H2) such that the class of (H1,H2)-free graphs have bounded clique-width.
The joint work we did leads to a couple of joint papers. The paper titled “Narrowing the Complexity Gap for Colouring ( , ) s t C P -Free Graphs” has appeared in the proceeding of AAIM 2014 while the paper “Bounding Clique-Width via Perfect Graphs” has been accepted by LATA 2015, which is to appear next March. Currently, Daniel, Konard and I are continuing the study of clique-width and we expect to obtain some further interesting results.
It was a wonderful experience to cooperate with scholars from other institutions. Not only does it help to advance our knowledge in a more efficient way, it also provides me the opportunity to learn from more experienced researchers in terms of how to ask questions. Sometimes it is more difficult to find a good problem than to solve one.
Tags: Student Voices