Frugal Colouring of Graphs

Details Frugal Colouring of Graphs Frugal Colouring of Graphs

2007-05-03

arxiv.org/abs/0705.0422v1

Computer Science

Discrete Mathematics

Scientific paper

A $k$-frugal colouring of a graph $G$ is a proper colouring of the vertices of $G$ such that no colour appears more than $k$ times in the neighbourhood of a vertex. This type of colouring was introduced by Hind, Molloy and Reed in 1997. In this paper, we study the frugal chromatic number of planar graphs, planar graphs with large girth, and outerplanar graphs, and relate this parameter with several well-studied colourings, such as colouring of the square, cyclic colouring, and $L(p,q)$-labelling. We also study frugal edge-colourings of multigraphs.

Affiliated with

Also associated with

No associations

Rating

Frugal Colouring 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 Frugal Colouring of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Frugal Colouring of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-496982