M. Shalu

activity

20112024

most citedStar Colouring of Bounded Degree Graphs and Regular Graphs

5 citations · 6 across the 6 of their papers we have counts for

collaborators

7 papers

cs.DM2024★ 1 cited

Open Packing in Graphs: Bounds and Complexity

M. A. Shalu, V. K. Kirubakaran

Given a graph $G (V, E)$ , a vertex subset $S$ of $G$ is called an open packing in $G$ if no pair of distinct vertices in $S$ have a common neighbour in $G$ . The size of a largest ope…

math.CO2023

Star colouring and locally constrained graph homomorphisms

Cyriac Antony, Shalu M. A

We relate star colouring of even-degree regular graphs to the notions of locally constrained graph homomorphisms to the oriented line graph $L (K_{q})$ of the complete graph $…

math.CO2023

Hardness Transitions and Uniqueness of Acyclic Colouring

Shalu M. A., Cyriac Antony

For $k \in N$ , a $k$ -acyclic colouring of a graph $G$ is a function $f : V (G) \to {0, 1, \dots, k - 1}$ such that (i)~ $f (u) \neq = f (v)$ for every edge $uv$ of $G$ , and (ii)~t…

math.CO2023

Hardness Transitions of Star Colouring and Restricted Star Colouring

Shalu M. A., Cyriac Antony

We study how the complexity of the graph colouring problems star colouring and restricted star colouring vary with the maximum degree of the graph. Restricted star colouring (in sh…

math.CO2023★ 5 cited

Star Colouring of Bounded Degree Graphs and Regular Graphs

Shalu M. A., Cyriac Antony

A $k$ -star colouring of a graph $G$ is a function $f : V (G) \to {0, 1, \dots, k - 1}$ such that $f (u) \neq = f (v)$ for every edge $uv$ of $G$ , and every bicoloured connected subgraph of $G$ …

math.CO2021

Complexity of Restricted Star Colouring

Shalu M. A., Cyriac Antony

Restricted star colouring is a variant of star colouring introduced to design heuristic algorithms to estimate sparse Hessian matrices. For $k \in N$ , a $k$ -restricted star…

cs.CC2011

The Two Bicliques Problem is in NP intersection coNP

M. A. Shalu, S. Vijayakumar

We show that the problem of deciding whether the vertex set of a graph can be covered with at most two bicliques is in NP $\cap$ coNP. We thus almost determine the computational comp…