Locally identifying coloring of graphs

Details Locally identifying coloring of graphs Locally identifying coloring of graphs

2010-10-27

arxiv.org/abs/1010.5624v1

Computer Science

Discrete Mathematics

19 pages

Scientific paper

A vertex-coloring of a graph G is said to be locally identifying if for any pair (u,v) of adjacent vertices of G, with distinct closed neighborhood, the set of colors that appears in the closed neighborhoods of u and v are distinct. In this paper, we give several bounds on the minimum number of colors needed in such a coloring for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether a subcubic bipartite graph with large girth has a locally identifying coloring with 3 colors is an NP-complete problem.

Affiliated with

Also associated with

No associations

Rating

Locally identifying coloring of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Locally identifying coloring of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Locally identifying coloring of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-485311