Metric Coloring of Pencil Graphs

Abstract

A graph is defined as an ordered pair (V,E), where V is a non-empty set of elements called vertices, and E is a set of edges that are finite and may be empty. Each edge connects two distinct vertices from V(G). Let f:V(G)→{1,2,3,…,k} be a coloring of the vertices of graph G, where two adjacent vertices can be colored with the same color. Considering the set of color classes Π={C_1,C_2,…,C_k}, for a vertex v in G, the color representation of v is a k-vector r(Π)=(d(v,C_1 ),d(v,C_2 ),…,d(v,C_k )),, where d(v,C_1 )=min⁡{d(v,c)∶c∈C_1}. If r(u | Π )≠r(v | Π ) for every two adjacent vertices u and v in G, the coloring is called a metric coloring of G. Thus, it can be concluded that two adjacent vertices u and v can be colored with the same color if their metric code conditions are different. The minimum number of the metric coloring is called as metric chromatic number. The goal of this research is analizing the metric chromatic number of the pencil graph. This graph was chosen because no previous research had been carried out on this graph. The proof begins by determining the lower bound, then determining the upper bound by checking coloring function and checking the metric coloring function and the metric code function of each vertex. In this research, we got the exact value of metric chromatic number of several type of pencil graph.