Perfectly Colorable Graphs

Details Perfectly Colorable Graphs Perfectly Colorable Graphs

2011-01-18

arxiv.org/abs/1101.3494v3

Information Processing Letters 111, 19, 960 - 961, 2011

Mathematics

Combinatorics

2 pages, 1 figure

Scientific paper

10.1016/j.ipl.2011.07.001.

We define a perfect coloring of a graph $G$ as a proper coloring of $G$ such that every connected induced subgraph $H$ of $G$ uses exactly $\omega(H)$ many colors where $\omega(H)$ is the clique number of $H$. A graph is perfectly colorable if it admits a perfect coloring. We show that the class of perfectly colorable graphs is exactly the class of perfect paw-free graphs. It follows that perfectly colorable graphs can be recognized and colored in linear time.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-287171