5 papers
On Vertex Bisection Width of Random -Regular Graphs
Josep Díaz, Öznur Yaşar Diner, Maria Serna +1
Vertex bisection is a graph partitioning problem in which the aim is to find a partition into two equal parts that minimizes the number of vertices in one partition set that have a…
The Multicolored Graph Realization Problem
Josep Díaz, Öznur Yaşar Diner, Maria Serna +1
We introduce the Multicolored Graph Realization problem (MGRP). The input to the problem is a colored graph , i.e., a graph together with a coloring on its vertices. We can…
Block Elimination Distance
Öznur Yaşar Diner, Archontia C. Giannopoulou, Giannos Stamoulis +1
We introduce the block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class , the class ${\cal B}({\cal…
On List k-Coloring Convex Bipartite Graphs
Josep Díaz, Öznur Yaşar Diner, Maria Serna +1
List k-Coloring (Li k-Col) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..,k…
Contraction and Deletion Blockers for Perfect Graphs and -free Graphs
Öznur Yaşar Diner, Daniël Paulusma, Christophe Picouleau +1
We study the following problem: for given integers , and graph , can we reduce some fixed graph parameter of by at least via at most graph operations from…