Majestic $t$-Tone Colorings of Bipartite Graphs with Large Cycles

Abstract

For a positive integer $k,$ let $[k]=1,2,\dots ,k$, let $P([k])$ denote the power set of the set $[k]$ and let $P\ast ([k])=P([k])–\mathrm{\varnothing }$. For each integer $t$ with $1\le t<k$, let $P_t([k])$ denote the set of $t$-element subsets of $P([k])$. For an edge coloring $c:E(G)\to P_t([k])$ of a graph $G$, where adjacent edges may be colored the same, $c^{\prime }:V(G)\to P\ast ([k])$ is the vertex coloring in which $c^{\prime }(v)$ is the union of the color sets of the edges incident with $v$. If $c^{\prime }$ 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 $ma{j}_t(G)$ of $G$. It is known that if $G$ is a connected bipartite graph or order at least 3, then $ma{j}_t(G)=t+1$ or $ma{j}_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 $l$ where where $n-5\le l\le n$ and $t\ge 2$ is an integer, then $ma{j}_t(G)=t+1$ and (ii) there is a 2-connected bipartite graph F of arbitrarily large order n whose longest cycles have length n-6 and $ma{j}_2(F)=4$. Furthermore, it is shown for integers $k,t\ge 2$ that there exists a k-connected bipartite graph $G$ such that $ma{j}_t(G)=t+2$. Other results and open questions are also presented.