$b$-coloring of Cartesian Product of Trees
| Autor: | R. Balakrishnan, S. Francis Raj, T. Kavaskar |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Vertex (graph theory)
Discrete mathematics $b$-Continuity General Mathematics 010102 general mathematics 0102 computer and information sciences trees Cartesian product 01 natural sciences Graph Combinatorics B-coloring symbols.namesake $b$-Chromatic number 05C15 Integer 010201 computation theory & mathematics $b$-Spectrum symbols 0101 mathematics Mathematics |
| Zdroj: | Taiwanese J. Math. 20, no. 1 (2016), 1-11 |
| Popis: | A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $b(G)$ of $G$. The $b$-spectrum $S_b(G)$ of a graph $G$ is the set of positive integers $k$, $\chi(G) \leq k \leq b(G)$, for which $G$ has a $b$-coloring using $k$ colors. A graph $G$ is $b$-continuous if $S_b(G) = \{\chi(G), \ldots, b(G)\}$. It is known that for any two graphs $G$ and $H$, $b(G \Box H) \geq \max \{b(G), b(H)\}$, where $\Box$ stands for the Cartesian product. In this paper, we determine some families of graphs $G$ and $H$ for which $b(G \Box H) \geq b(G)+b(H)-1$. Further if $T_i$, $i = 1, 2, \ldots, n$, are trees with $b(T_i) \geq 3$, then $b(T_1 \Box \cdots \Box T_n) \geq \sum_{i=1}^{n} b(T_i)-(n-1)$ and $S_b(T_1 \Box \cdots \Box T_n) \supseteq \{2, \ldots, \sum_{i=1}^n b(T_i)-(n-1)\}$. Also if $b(T_i) = \Delta(T_i)+1$ for each $i$, then $b(T_1 \Box \cdots \Box T_n) = \Delta(T_1 \Box \cdots \Box T_n)+1$, and $T_1 \Box \cdots \Box T_n$ is $b$-continuous. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|