Search

The question of whether 3-Coloring can be solved in polynomial-time for the diameter two graphs is a well-known open problem in the area of algorithmic graph theory. We study the problem restricted to graph classes that avoid cycles of given lengths as induced subgraphs. Martin et. al. [CIAC 2021] showed that the problem is polynomial-time solvable for $C_5$-free or $C_6$-free graphs, and, $(C_4,C_s)$-free graphs where $s \in \{3,7,8,9\}$. We extend their result proving that it is polynomial-time solvable for $(C_4,C_s)$-free graphs, for any constant $s$, and for $(C_3,C_7)$-free graphs. Our results also hold for the more general problem List 3-Colouring., Comment: 14 pages. Revised version accepted to 18th Algorithms and Data Structures Symposium (WADS 2023)

A k-role coloring of a graph G is an assignment of k colors to the vertices of G such that if any two vertices are assigned the same color, then their neighborhood are assigned the same set of colors. By definition, every graph on n vertices admits an n-role coloring. While for every graph on n vertices, it is trivial to decide if it admits a 1-role coloring, determining whether a graph admits a k-role coloring is a notoriously hard problem for k greater than 1. In fact, it is known that k-Role coloring is NP-complete for k greater than 1 on arbitrary graphs. There has been extensive research on the complexity of k-role coloring on various hereditary graph classes. Furthering this direction of research, we show that k-Role coloring is NP-complete on bipartite graphs for k greater than 2 (while it is trivial for k = 2). We complement the hardness result by characterizing 3-role colorable bipartite chain graphs, leading to a polynomial-time algorithm for 3-Role coloring for this class of graphs. We further show that 2-Role coloring is NP-complete for graphs that are d vertices or edges away from the class of bipartite graphs, even when d = 1., Comment: 17 pages including references, 5 figures

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most $k$ vertices whose deletion results in a chordal graph, when parameterized by $k$. While this investigation fits naturally into the recent trend of what are called `structural parameterizations', here we assume that the deletion set is not given. One method to solve them is to compute a $k$-sized or an approximate ($f(k)$ sized, for a function $f$) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least $k^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ running time when we use the known parameterized or approximation algorithms for finding a $k$-sized chordal deletion set on an $n$ vertex graph. In this work, we design $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in time $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ where each bag is a union of four cliques and $\mathcal{O}(k)$ vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are adaptive (robust) in the sense that given an integer $k$, they detect whether the graph has a chordal vertex deletion set of size at most $k$ or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the Strong Exponential Time Hypothesis (SETH).