5 citations · 5 across the 7 of their papers we have counts for
7 papers · 1 filter
Some short notes on oriented line graphs and related matrices
Jacob Antony, Cyriac Antony, Jinitha Varughese +1
Oriented line graph, introduced by Kotani and Sunada (2000), is closely related to Hashimato's non-backtracking matrix (1989). It is known that for regular graphs , the eigenval…
Graceful coloring is computationally hard
Cyriac Antony, Laavanya D., Devi Yamini S
Given a (proper) vertex coloring of a graph , say , the difference edge labelling induced by is a function defin…
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 of the complete graph $…
Hardness Transitions and Uniqueness of Acyclic Colouring
Shalu M. A., Cyriac Antony
For , a -acyclic colouring of a graph is a function such that (i)~ for every edge of , and (ii)~t…
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…
Star Colouring of Bounded Degree Graphs and Regular Graphs
Shalu M. A., Cyriac Antony
A -star colouring of a graph is a function such that for every edge of , and every bicoloured connected subgraph of …
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 , a -restricted star…