On quasi-monotonous graphs

详细信息    查看全文

• 作者：Mekkia Kouider ^{mekkia.kouider@lri.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：b-coloring ; Chordal graphs ; Claw-free graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 January 2016
• 年：2016
• 卷：198
• 期：Complete
• 页码：155-163
• 全文大小：396 K

文摘

A dominating coloring   by k$k$ colors is a proper k$k$ coloring where every color i$i$ has a representative vertex x_i$x_i$ adjacent to at least one vertex in each of the other classes. The b-chromatic number  , b(G)$b\left(G\right)$, of a graph G$G$ is the largest integer k$k$ such that G$G$ admits a dominating coloring by k$k$ colors. A graph 2256d" title="Click to view the MathML source">G=(V,E)$G=(V,E)$ is said b-monotonous   if b(H₁)≥b(H₂)$b\left(H_1\right)\ge b\left(H_2\right)$ for every induced subgraph H₁$H_1$ of G$G$ and every subgraph H₂$H_2$ of H₁$H_1$. Here we say that a graph G$G$ is quasi b-monotonous  , or simply quasi-monotonous, if for every vertex v∈V$v\in V$, b(G−v)≤b(G)+1$b(G-v)\le b\left(G\right)+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)$(P,coP,chair,diamond)$-free graphs are quasi-monotonous. The (P₅,P,dart)$(P_5,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.