On Colorings of Squares of Outerplanar Graphs

Details On Colorings of Squares of Outerplanar Graphs On Colorings of Squares of Outerplanar Graphs

2007-06-11

arxiv.org/abs/0706.1526v1

Mathematics

Combinatorics

24 pages, 17 figures

Scientific paper

We study vertex colorings of the square $G^2$ of an outerplanar graph $G$. We find the optimal bound of the inductiveness, chromatic number and the clique number of $G^2$ as a function of the maximum degree $\Delta$ of $G$ for all $\Delta\in \nats$. As a bonus, we obtain the optimal bound of the choosability (or the list-chromatic number) of $G^2$ when $\Delta \geq 7$. In the case of chordal outerplanar graphs, we classify exactly which graphs have parameters exceeding the absolute minimum.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-179823