On multiset colorings of generalized corona graphs

Title:

On multiset colorings of generalized corona graphs

Creator:

Feng, Yun and Lin, Wensong

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:014318c7-5e47-4e4e-8081-dd3ff3a2b0f7
uuid:014318c7-5e47-4e4e-8081-dd3ff3a2b0f7
doi:10.21136/MB.2016.0053-14

Subject:

multiset coloring, multiset chromatic number, generalized corona of a graph, and neighbor-distinguishing coloring

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

A vertex k-coloring of a graph G is a multiset k-coloring if M(u) ≠ M(v) for every edge uv ∈ E(G), where M(u) and M(v) denote the multisets of colors of the neighbors of u and v, respectively. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χm(G) of G. For an integer l ≥ 0, the l-corona of a graph G, corl (G), is the graph obtained from G by adding, for each vertex v in G, l new neighbors which are end-vertices. In this paper, the multiset chromatic numbers are determined for l-coronas of all complete graphs, the regular complete multipartite graphs and the Cartesian product Kr K2 of Kr and K2. In addition, we show that the minimum l such that χm(corl (G)) = 2 never exceeds χ(G) − 2, where G is a regular graph and χ(G) is the chromatic number of G.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

431-455

Source:

Mathematica bohemica | 2016 Volume:141 | Number:4

Harvested from:

CDK

Metadata only:

false