Student Voices

Travel Report: Shenwei Huang, Computing, United Kingdom

December 19, 2014

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.

No comments yet

Recent Blog Posts

  • External Award: WorkSafeBC Innovation at Work Grants December 04, 2019
    The 2018 WorkSafe BC Innovation at Work competition launches November 3, 2017, with an application deadline in late January or early February. The award is generally $50,000 and is geared towards funding proposals that are innovative and practical.

  • Call for Proposal: 17th Symposium on Teaching and Learning March 01, 2019
    The SFU Teaching and Learning Centre invites interactive and innovative proposals that demonstrate how your practice, research, or scholarly inquiry relates to the theme of Assessing and Celebrating Teaching and Student Learning. Deadline: Mar 22

  • Tea Time Talk March 01, 2019
    Join the event on Mar 18 to enjoy afternoon tea while sharing with us a conversation on how SFU can foster a culture of fairness, belonging and diversity. RSVP now

View Posts by Category