Showing 2019Show all
3 papers · 1 filter
cs.DM2019
Hardness and approximation for the geodetic set problem in some graph classes
Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat +2
In this paper, we study the computational complexity of finding the \emph{geodetic number} of graphs. A set of vertices of a graph is a \emph{geodetic set} if any vertex of…
math.CO2019
On Colourability of Polygon Visibility Graphs
Onur Çağirici, Petr Hliněný, Bodhayan Roy
We study the problem of colouring visibility graphs of polygons. In particular, for visibility graphs of simple polygons, we provide a polynomial algorithm for 4-colouring, and pro…
cs.CG2019
On conflict-free chromatic guarding of simple polygons
Onur Çağırıcı, Subir Kumar Ghosh, Petr Hliněný +1
We study the problem of colouring the vertices of a polygon, such that every viewer in it can see a unique colour. The goal is to minimise the number of colours used. This is also…