7 papers · 1 filter
Almost Empty Monochromatic Polygons in Planar Point Sets
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam +2
For integers , , and , let denote the smallest integer such that any set of at least points in th…
Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound
Sandip Das, Sk Samim Islam, Aashirwad Mohapatra +2
A strong edge colouring of a graph is an edge colouring in which every colour class is an induced matching. The minimum number of colours is the strong chromatic index $χ'_s(G)…
Large Planar Point Sets Contain 4 Collinear Points or Almost 7-Cliques, and Related Results
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam +2
We prove that every sufficiently large finite planar point set contains either four collinear points or seven points with at most one non-visible pair. More generally, we show that…
An Improved Upper Bound for the Turán Number of the Hexagon
Sandip Das, Sk Samim Islam, Aashirwad Mohapatra +1
For a graph , the Turán number is the maximum number of edges in an -vertex graph containing no copy of . Determining the Turán numbers of even cy…
Exact-Distance Domination in Grid Graphs
Sandip Das, Sweta Das, Arpan Sadhukhan
Let be the square grid, and let . A set is an \emph{exact-distance -dominating set} if every vertex has a…
Parameterized complexity of -Hop, -Step, and -Hop Roman Domination
Sandip Das, Sweta Das, Sk Samim Islam
The \textsc{Dominating Set} problem is a classical and extensively studied topic in graph theory and theoretical computer science. In this paper, we examine the algorithmic complex…
On the Number of Almost Empty Monochromatic Triangles
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam +3
In this paper, we consider the problem of counting almost empty monochromatic triangles in colored planar point sets, that is, triangles whose vertices are all assigned the same co…