In NetHack, murder is the act of killing a formerly peaceful human such as a watchman, shopkeeper, or aligned priest. This only applies to humans who were generated as peaceful, not to those who were generated as hostile then pacified through magic. In particular, Keystone Kops do not count because they are generated hostile. Also, if you anger the high priest of Moloch by entering his temple, you may kill him without being considered a murderer. Killing him from outside the temple, without first entering the temple, still counts. If the high priest has called you an infidel, he is fair game. Killing a guard is murder, even if the guard attacks first.
Note that whatever your race, only the killing of a peaceful human will ever be classed as murder.
The simplest way to get rid of a peaceful human while avoiding the penalty for murder is to let your pet do the dirty work. You can also polymorph your victims before killing them. Note that a failed polymorph, "<human> shudders." (system shock), still counts as murder.