List homomorphisms and bipartite co-circular arc graphs

In the study of the list homomorphisms, the class of bipartite co-circular arc graphs plays an important role in delineating easy (polynomial) cases and hard (NP-complete) cases of the list homomorphism problem. This class of graphs has many equivalent characterizations, and we present (at the beginning of Chapter 4) a new short proof of some of these equivalences. We then discuss possible approaches to the recognition problem for this class of graphs. First we discuss the linear time recognition algorithms of circular arc graphs by Eschen-Spinrad, McConnell and Nussbaum-Kaplan. These may be applied to the complementary graph, but the algorithm is no longer linear. The main new contributions contained in this thesis are efficient algorithms for the recognition of co-circular arc graphs in the special cases of trees, $k$-trees and bounded degree graphs (see Chapter 3). We also present new efficient algorithms for colouring, matching, and other similar problems on this class of graphs (see Chapter 4).