Search

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set {1, . . . , k}. These colors can be used to distinguish adjacent vertices of G. There are many possibilities of such a distinction. In this paper, we focus on the one by the full sum of colors of a vertex, i.e., the sum of the color of the vertex, the colors on its incident edges and the colors on its adjacent vertices.

A total k-weighting f of a graph G is an assignment of integers from the set {1, . . . , k} to the vertices and edges of G. We say that f is neighbor expanded sum distinguishing, or NESD for short, if Σw∈N(v) (f(vw) + f(w)) differs from Σw∈N(u)(f(uw) + f(w)) for every two adjacent vertices v and u of G. The neighbor expanded sum distinguishing index of G, denoted by egndiΣ(G), is the minimum positive integer k for which there exists an NESD weighting of G. An NESD weighting was introduced and investigated by Flandrin et al. (2017), where they conjectured that egndiΣ(G) ≤ 2 for any graph G. They examined some special classes of graphs, while proving that egndiΣ(G) ≤ χ(G) + 1. We improve this bound and show that egndiΣ(G) ≤ 3 for any graph G. We also show that the conjecture holds for all bipartite, 3-regular and 4-regular graphs.

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.

Let G be a simple graph. For a general edge coloring of a graph G (i.e., not necessarily a proper edge coloring) and a vertex v of G, denote by S( v) the set (not a multiset) of colors used to color the edges incident to v. For a general edge coloring f of a graph G, if S( u) ≠ S( v) for any two different vertices u and v of G, then we say that f is a point-distinguishing general edge coloring of G. The minimum number of colors required for a point-distinguishing general edge coloring of G, denoted by χ( G), is called the point-distinguishing chromatic index of G. In this paper, we determine the point-distinguishing chromatic index of the union of paths and propose a conjecture. [ABSTRACT FROM AUTHOR]