Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872035 | Discrete Applied Mathematics | 2016 | 9 Pages |
Abstract
A dominating coloring by k colors is a proper k coloring where every color i has a representative vertex xi adjacent to at least one vertex in each of the other classes. The b-chromatic number, b(G), of a graph G is the largest integer k such that G admits a dominating coloring by k colors. A graph G=(V,E) is said b-monotonous if b(H1)â¥b(H2) for every induced subgraph H1 of G and every subgraph H2 of H1. Here we say that a graph G is quasi b-monotonous, or simply quasi-monotonous, if for every vertex vâV, b(Gâv)â¤b(G)+1. We shall study the quasi-monotonicity of several classes. We show in particular that chordal graphs are not quasi-monotonous in general, whereas chordal graphs with large b-chromatic number, and (P,coP,chair,diamond)-free graphs are quasi-monotonous. The (P5,P,dart)-free graphs are monotonous. Finally we give new bounds for the b-chromatic number of any vertex deleted subgraph of a chordal graph.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mekkia Kouider,