- Tytuł:
- Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree
- Autorzy:
-
Dong, Aijun
Zhang, Xin - Powiązania:
- https://bibliotekanauki.pl/articles/31342275.pdf
- Data publikacji:
- 2018-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph coloring
equitable choosability
maximum average degree - Opis:
- A graph is said to be equitably $k$-colorable if the vertex set $V (G)$ can be partitioned into $k$ independent subsets $ V_1, V_2, . . ., V_k $ such that $ | | V_i |−| V_j | | \le 1 $ $(1 \le i, j \le k) $. A graph $G$ is equitably $k$-choosable if, for any given $k$-uniform list assignment $L$, $G$ is $L$-colorable and each color appears on at most $ \ceil{ \frac{|V(G)|}{ k } } $ vertices. In this paper, we prove that if $G$ is a graph such that $ mad(G) < 3 $, then $G$ is equitably $k$-colorable and equitably $k$- choosable where $ k \ge \text{max} \{ \Delta (G), 4 \} $. Moreover, if $G$ is a graph such that $ mad(G) < \frac{12}{5} $, then $G$ is equitably $k$-colorable and equitably $k$-choosable where $ k \ge \text{max} \{ \Delta (G), 3 \} $.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 829-839
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł