Locally harmonious coloring is a relax version of standard harmonious coloring which only needs that the color pairs for adjacent edges are different. In this remark, we introduce the concept of fractional locally harmonious coloring, and present some basic facts for this coloring.
Let \(G=(V,E)\) be a graph, where \(V(G)\) and \(E(G)\) are denoted as the vertex set and the edge set of \(G\), respectively. All graphs considered in this paper are finite, loopless, and without multiple edges. Notations and terminologies used but undefined in this paper can be found in Bondy and Mutry [1].
Graph coloring can be regarded as a special case of graph labeling, and it is an assignment of labels called “colors” to
elements of a graph subject to certain constraints. Specifically, we present some examples below:
\(\bullet\) vertex coloring (or, called proper vertex coloring), assigns colors to each vertex of a graph so that no two adjacent vertices will be assigned with the same color. A vertex coloring of a graph with \(k\) or fewer colors is known as a \(k\)-coloring, and this graph is said to be a \(k\)-colorable graph. The chromatic number of a graph \(G\) (denoted by \(\chi(G)\)) is the smallest value of \(k\) possible to obtain a \(k\)-coloring.
\(\bullet\) total coloring, assigning colors to each vertex and each edge of a graph so that no adjacent elements are assigned the same color. The total chromatic number \(\chi”(G)\) of a graph \(G\) is the smallest number of colors needed in the total coloring
of \(G\).
\(\bullet\) harmonious coloring, is a proper vertex coloring of a graph \(G\) that each pair of colors appears on at most one edge. The harmonious chromatic number of \(G\), \(\chi_{h}(G)\), is the minimum number of colors needed for the harmonious coloring of \(G\).
\(\bullet\) fractional coloring, is a branch of fractional theory (see Scheinesrman and Ullman [2] for more
details). The \(a:b\) coloring of a graph, i.e., assigns each vertex \(v\) a set \(C_{v}\in\{1,\cdots,a\}\) meets \(|C_{v}|=b\), and
\(C_{v}\cap C_{v’}=\emptyset\) if \(vv’\in E(G)\). Then. such \(a:b\) coloring is just the fractional color of graph \(G\). The
corresponding fractional chromatic number \(\chi_{f}(G)\) is defined by
$$\chi_{f}(G)=\inf\{\frac{a}{b}| G\quad {\rm exists\quad a}\quad a:b\quad {\rm coloring}\}.$$
\(\bullet\) fractional total coloring, is a combination of fractional coloring and total coloring (see Kilakos and Reed
[3] for more details). We say that a graph \(G\) is \(\frac{a}{b}\)-fractional total colorable if there exist a
fractional \(\frac{a}{b}\)-coloring of the total graph of \(G\). The fractional total chromatic number \(\chi_{f}^{”}(G)\) of a graph
\(G\) is the smallest number of fractional coloring needed in its total graph.
\(\bullet\) \(n’\)-path distinguishing coloring, see Harary [4] for more details, is a class of proper
coloring in which all vertices are colored different in each path \(P_{n’}\) of length \(n’\). The corresponding \(n’\)-path
distinguishing chromatic number \(\chi_{P_{n’}}^{”}(G)\) of a graph \(G\) is the smallest number of \(n’\)-path distinguishing
coloring needed in \(G\).
Harmonious coloring, as an important topic of graph coloring, has raised much attention among the researchers. Hopcroft and Krisnamoorthy [5] first introduced the concept of harmonious coloring, and showed that the harmonious coloring problem for general graphs is NP-complete. Lee and Mitchum [6] presented an upper bound for the harmonious chromatic number of a graph. Miller and Pritikin [7] constructed efficient harmonious colorings of complete binary trees, 2 and 3-dimensional grids, and \(n\)-dimensional cubes. Ioannidou and Nikolopoulos [8] studied the harmonious coloring on subclasses of colinear graphs. Hegde and Castelino [9] investigated the proper harmonious coloring number of graphs such as alternating paths and alternating cycles. Venkatachalam et al. [10] reported the harmonious chromatic number for the central graph, middle graph, total graph and line graph of double star graph \(K_{1,n,n}\), and they proved that for the line graph of double star graph, the harmonious chromatic number and the achromatic number are equal. Furthermore, this result can be extended by classifying the different families of graphs for which these two numbers are equal. Akbari et al. [12] obtained the harmonious coloring of trees with large maximum degree \(\ge\frac{n+2}{3}\). Edwards [13] gave an upper bound for the harmonious chromatic number of a general directed graph, and showed that determining the exact value of the harmonious chromatic number is NP-hard for directed graphs of bounded degree. Muntaner-Batle et al. [14] found the harmonious chromatic number of the corona product of any graph $G$ of order $l$ with the complete graph \(K_{n}\) for \(l\le n\). As a consequence of this work, then also obtained the harmonious chromatic number of \(t\) copies of \(K_{n}\) for \(t\le n+1\). Hegde and Castelino [14] investigated the proper harmonious coloring number of graphs such as unidirectional paths, unicycles, inspoken and outspoken wheels, \(n\)-ary trees of different levels etc.
However, the standard harmonious coloring is much difficult than any other kind of graph coloring. From this point of view, a relax version of harmonious coloring was introduced as locally harmonious coloring. The locally harmonious coloring is a kind of proper vertex coloring which only needs that the adjacent edges have different color pairs, i.e., for each vertex \(v\), its adjacent vertices are all colored different (no two vertices in \(N(v)\) colored the same). The locally harmonious chromatic number of \(G\) denoted by \(\chi_{LH}(G)\) is the smallest number \(k\) that \(G\) admits a \(k\)-locally harmonious coloring.
In this paper, we further consider the locally harmonious coloring, and introduce an extension coloring concept. The fractional locally harmonious coloring is the rational approach to locally harmonious coloring so that each vertex \(v\) in a graph \(G\) assigns a collection with \(b\) element from \(\{1,\cdots,a\}\) denoted by \(C_{v}\), we have \(C_{v}\cap C_{v’}=\emptyset\) if \(vv’\in E(G)\), and \(C_{v’}\cap C_{v”}=\emptyset\) if \(v’\) and \(v”\) adjacent to the same vertex \(v\). The fractional locally harmonious chromatic number of \(G\) denoted by \(\chi_{FLH}(G)\) is the smallest rational number \(\frac{a}{b}\) so that \(G\) admits a \(\frac{a}{b}\)-fractional locally harmonious coloring. Obviously, we have \(\chi_{FLH}(G)\le \chi_{LH}(G)\) for any graph \(G\) and the fractional locally harmonious coloring problem for general graphs is also NP-complete.
Theorem 2.1. Let \(D(G)\) be the diameter of graph \(G\). Then, \(\chi_{FLH}(G)=|V(G)|\Leftrightarrow D(G)\le2\).
Proof. For the necessity. If \(\chi_{FLH}(G)=|V(G)|\) but \(D(G)\ge3\), then there exist two vertices \(u,v\in V(G)\) satisfying \(d(u,v)\ge3\). Thus, by assigning the same color to \(u\) and \(v\), we infer that \(\chi_{LH}(G)\le|V(G)|-1< |V(G)|\). Hence, \(\chi_{FLH}(G)\le\chi_{LH}(G)< |V(G)| \), a contradiction.
For the sufficiency, we assume that \(D(G)\le2\) and \(C\) is a
fractional locally harmonious coloring of \(G\). Let \(C_{v}\) be the collection of elements assigned to vertex \(v\).
\(\bullet\) If \(D(G)=1\), then \(G\cong K_{|V(G)|}\). Clearly, we
have \(\chi_{FLH}(G)=|V(G)|\).
\(\bullet\) If \(D(G)=2\), then there are two situations for any two
vertices \(u,v\in V(G)\). 1) If \(uv\in E(G)\), the \(C_{u}\cap
C_{v}=\emptyset\). 2) If \(uv\notin E(G)\), by means of \(D(G)=2\),
there exists a vertex \(w\) such that \(uw\in E(G)\) and \(vw\in E(G)\).
Using the definition of fractional locally harmonious coloring, we
infer that \(C_{u}\cap C_{v}=\emptyset\).
From the above discussion, we summarize that \(C_{u}\cap C_{v}=\emptyset\) for any two vertices \(u,v\in V(G)\). Therefore, \(\chi_{FLH}(G)=|V(G)|\).
Now, we extend the \(n’\)-path distinguishing coloring to its fractional version. Assign each vertex \(v\) a set \(C_{v}\in\{1,\cdots,a\}\) such that \(|C_{v}|=b\), and \(C_{v}\cap C_{v’}=\emptyset\) if \(vv’\in E(G)\). The \(a:b\) fractional \(n’\)-path distinguishing coloring is defined as the fractional coloring of graph \(G\) such that \(C_{v}\cap C_{v’}=\emptyset\) for any two vertices \(v,v’\in P_{n’}\) with \(P_{n’}=n’\). The corresponding fractional \(n’\)-path distinguishing chromatic number \(\chi_{FP_{n’}}(G)\) is defined as mimimum \(\frac{a}{b}\) such that \(G\) has \(\frac{a}{b}\)-fractional \(n’\)-path distinguishing coloring. The second main result in our remark is stated as follows which presented the equivalence between \(\frac{a}{b}\)-fractional locally harmonious coloring and \(\frac{a}{b}\)-fractional \(3\)-path distinguishing coloring.
Theorem 2.2. A graph \(G\) can be \(\frac{a}{b}\)-fractional locally harmonious coloring if and only if it has \(\frac{a}{b}\)-fractional \(3\)-path distinguishing coloring, i.e., $$\chi_{FLH}(G)=\frac{a}{b}\Leftrightarrow \chi_{FP_{3}}(G)=\frac{a}{b}.$$
Proof. For the necessity. Since \(G\) is \(\frac{a}{b}\)-fractional locally harmonious colorable, we infer that \(C_{v_{1}}\cap C_{v_{2}}=\emptyset\) for each \(v\in V(G)\) and \(v_{1},v_{2}\in N[v]\). Hence, for any 3-path \(P_{3}\triangleq v_{1}v_{2}v_{3}\), we have \(v_{1},v_{3}\in N[v_{2}]\), and the intersection of assigned collection of \(v_{1},v_{2},v_{3}\) is \(\emptyset\), i.e., \(G\) is \(\frac{a}{b}\)-fractional \(3\)-path distinguishing colorable.
For the sufficiency. Assume that \(G\) is \(\frac{a}{b}\)-fractional \(3\)-path distinguishing colorable, but not a \(\frac{a}{b}\)-fractional locally harmonious coloring graph. Then, there exist a vertex \(v\in V(G)\), and \(v_{1},v_{2}\in N[v]\) such that \(C_{v_{1}}\cap C_{v_{2}}\ne\emptyset\). This contracts that \(v_{1},v,v_{2}\) in a \(P_{3}\) path.
For the relationship between cut vertex and fractional locally harmonious coloring, we present the following conclusion.Theorem 2.3. Let \(u\) be a cut vertex of graph \(G\), and \(G_{i}^{‘} (i=1,\cdots,t)\) be the branches of \(G-\{u\}\). Let \(N_{G}[u]=N_{G}(u)\cup\{u\}\). Set $$G_{i}=G[V(G_{i}^{‘})\cup N_{G}[u]]$$ for \(i=1,\cdots,t\). Then, we have $$\chi_{FLH}(G)=\max\{\chi_{FLH}(G_{i}),i=1,\cdots,t\}\triangleq\frac{a}{b}.$$
Proof. Let \(i_{i}=\{i|\chi_{FLH}(G_{i})=\frac{a}{b},i=1,\cdots,t\}\). First, we \(\frac{a}{b}\)-fractional locally harmonious coloring one of \(G_{i_{0}}\) which denoted by \(C_{1}\). Then, \(\frac{a}{b}\)-fractional locally harmonious coloring the rest \(G_{i}\) one by one so that the collection assigned for the vertices in \(N_{G}[u]\) is the same with the collection assigned to these vertices under \(C_{1}\), and such colorings are denoted by \(C_{i} (i=2,\cdots,t)\) which exist obviously. Finally, set \(C=\cup_{i=1}^{t}C_{i}\). Thus, we get the desired \(\frac{a}{b}\)-fractional locally harmonious coloring.
The following conclusion reveals the fractional locally harmonious chromatic number of cycle, and we skip the detail proof.
Theorem 2.4. Let \(C_{n}\) be a cycle of order \(n\). Then, $$\chi_{FLH}(C_{n})=\left\{\begin{array}{ll}n,& \hbox{if $n\le5$} \\ \frac{n}{k},& \hbox{if $n\ge6$ and $k=\lfloor\frac{n}{3}\rfloor$}. \end{array}\right.$$
The following corollaries are deduced immediately from Theorem 2.4.Theorem 2.5. If \(n\equiv0\)(mod 3), then \(\chi_{FLH}(C_{n})=3\).
Corollary 2.6. If \(n\ge6\), then \(3\le \chi_{FLH}(C_{n})\le4\).
3. Conclusion Graph coloring theory is the core research contents of graph theory. It has important applications in optimization theory, task scheduling, and computer networks. In this remark, we give the new concept called fractional locally harmonious coloring, and determine several properties for this coloring.
