On the vertex-distinguishing proper edge coloring of composition of complete graph and star

A proper k-edge coloring of a simple graph G is called k-vertex-distinguishing proper edge coloring (k-VDPEC) if for any two distinct vertices u and v of G, the set of colors assigned to edges incident to u differs from the set of colors assigned to edges incident to v. The minimum number of colors...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2014-04, Vol.114 (4), p.217-221
Main Authors: Yang, Fang, Chen, Xiang-en, Ma, Chunyan
Format: Article
Language:English
Subjects:
Coloring
Combinatorial problems
Complete graph
Composition
Data processing
Graph coloring
Graph theory
Graphs
Information processing
Star
Stars
Studies
Vertex-distinguishing proper edge chromatic number
Vertex-distinguishing proper edge coloring
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A proper k-edge coloring of a simple graph G is called k-vertex-distinguishing proper edge coloring (k-VDPEC) if for any two distinct vertices u and v of G, the set of colors assigned to edges incident to u differs from the set of colors assigned to edges incident to v. The minimum number of colors required for a vertex-distinguishing proper edge coloring of G, denoted by χs′(G), is called the vertex-distinguishing proper edge chromatic number. For p⩾2 and q⩾4, we will obtain vertex-distinguishing proper edge chromatic number of composition of complete graph Kp with order p and star Sq with order q, which is pq. •Coloring problem in graph theory research has important theoretical significance and application value.•The vertex-distinguishing proper edge coloring is interesting and difficult problem.•Determining chromatic number of various kinds of colorings is a fundamental problem of graph coloring.•For p⩾2 and q⩾4, we will obtain vertex-distinguishing proper edge chromatic numbers of Kp[Sq] in this paper.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2013.11.001