3 papers
cs.DS2023
3-Coloring or -free Diameter Two Graphs
Tereza Klimošová, Vibha Sahlot
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 p…
cs.DS2021
Role Coloring Bipartite Graphs
Sukanya Pandey, Vibha Sahlot
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…
cs.DS2020
Structural Parameterizations with Modulator Oblivion
Ashwin Jacob, Fahad Panolan, Venkatesh Raman +1
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 i…