List homomorphisms and bipartite co-circular arc graphs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2012-07-31
Authors/Contributors
Author: Ershadi, Ali
Abstract
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).
Document
Identifier
etd7304
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Hell, Pavol
Member of collection
Attachment Size
etd7304_AErshadi.pdf 537.61 KB