Skip to main content

List matrix partitions of special graphs

Resource type
Thesis type
(Thesis) Ph.D.
Date created
Let M be a symmetric m x m matrix with entries from the set {0,1,*\}. The M -partition problem asks whether the vertices of a given graph G can be partitioned into m parts V_0,V_1...V_m-1 such that any two distinct vertices in (possibly equal) parts V_i\ and V_j are adjacent if M(i,j)=1, and non-adjacent if M(i,j)=0. This problem generalizes k-coloring and H-coloring problems, as well as many other well-known graph problems. In its list version, which is called the list M -partition problem, a list is assigned to each vertex to restrict its placement into certain parts. An open problem, called the dichotomy problem, asks whether each (list) M -partition problem is polynomial or NP-complete. The difficulty of this problem led to the study of restrictions on the input graphs. A secondary goal was to identify the well-known graph classes for which all (list) M partition problems are polynomial. Several graph classes including perfect graphs, chordal graphs, etc. have been studied so far. In this thesis we continue this line of research, focusing mainly on the list version. We identify certain graph classes defined in terms of geometric configurations, and we prove that for these classes all list M -partition problems are polynomial. These classes include such well-known classes as interval and circular arc graphs. We also consider other standard graphs classes including some generalizations of the aforementioned classes, line graphs and their extensions to quasi-line graphs and claw-free graphs, and some special cases of H-free graphs. For these classes we provide a positive answer to the dichotomy problem for certain kinds of matrices M .
Copyright statement
Copyright is held by the author.
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
Thesis advisor: Tardos, Gabor
Member of collection
Download file Size
etd7865_PValadkhan.pdf 1.29 MB

Views & downloads - as of June 2023

Views: 8
Downloads: 1