Majestic t-Tone Colorings of Bipartite Graphs with Large Cycles

摘要

For a positive integer k, let [k] = {1,2,…k}. let P([k]) denote the power set of the set [k] and let P~*([k]) = P([k]) - {Φ}. For each integer t with 1 ≤ t < k, let P_t([k]) denote the set of t-element subsets of P([k]). For an edge coloring c : E(G) → P_t([k]) of a graph G, where adjacent edges may be colored the same, c' : V(G) →P*([k]) is the vertex coloring in which c'(ⅴ) is the union of the color sets of the edges incident with v. If c' is a proper vertex coloring of G, then c is a majestic t-tone k-coloring of G. For a fixed positive integer t, the minimum positive integer k for which a graph G has a majestic t-tone k-coloring is the majestic t-tone index maj_t(G) of G. It is known that if G is a connected bipartite graph of order at least 3, then maj_t(G) = t + 1 or maj_t(G) = t + 2 for each positive integer t. It is shown that (i) if G is a 2-connected bipartite graph of arbitrarily large order n whose longest cycles have length e where n - 5 ≤ e≤ n and t ≥ 2 is an integer, then maj_t(G) = t + 1 and (ⅱ) there is a 2-connected bipartite graph F of arbitrarily large order n whose longest cycles have length n-6 and maj_2(F) = 4. Furthermore, it is shown for integers k, t ≥ 2 that there exists a k-connected bipartite graph G such that maj_t(G) = t + 2. Other results and open questions are also presented.