- Tytuł:
- On multiset colorings of graphs
- Autorzy:
-
Okamoto, Futaba
Salehi, Ebrahim
Zhang, Ping - Powiązania:
- https://bibliotekanauki.pl/articles/744555.pdf
- Data publikacji:
- 2010
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
vertex coloring
multiset coloring
neighbor-distinguishing coloring - Opis:
- A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χₘ(G) of G. For every graph G, χₘ(G) is bounded above by its chromatic number χ(G). The multiset chromatic numbers of regular graphs are investigated. It is shown that for every pair k, r of integers with 2 ≤ k ≤ r - 1, there exists an r-regular graph with multiset chromatic number k. It is also shown that for every positive integer N, there is an r-regular graph G such that χ(G) - χₘ(G) = N. In particular, it is shown that χₘ(Kₙ × K₂) is asymptotically √n. In fact, $χₘ(Kₙ × K₂) = χₘ(cor(K_{n+1}))$. The corona cor(G) of a graph G is the graph obtained from G by adding, for each vertex v in G, a new vertex v' and the edge vv'. It is shown that χₘ(cor(G)) ≤ χₘ(G) for every nontrivial connected graph G. The multiset chromatic numbers of the corona of all complete graphs are determined. On Multiset Colorings of Graphs From this, it follows that for every positive integer N, there exists a graph G such that χₘ(G) - χₘ(cor(G)) ≥ N. The result obtained on the multiset chromatic number of the corona of complete graphs is then extended to the corona of all regular complete multipartite graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 137-153
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł