Menu
For a connected graph \(G\) of order at least \(3\), let \(c : E(G) \to \{1, 2, \dots, k\}\) be an edge coloring of \(G\) where adjacent edges may be colored the same. Then \(c\) induces a vertex coloring \(c’\) of \(G\) by assigning to each vertex \(v\) of \(G\) the set of colors of the edges incident with \(v\). The edge coloring \(c\) is called a majestic \(k\)-edge coloring of \(G\) if the induced vertex coloring \(c’\) is a proper vertex coloring of \(G\). The minimum positive integer \(k\) for which a graph \(G\) has a majestic \(k\)-edge coloring is the majestic chromatic index of \(G\) and denoted by \(\chi_{m}^{‘} (G)\). For a graph \(G\) with \(\chi_{m}^{‘}(G) = k\), the minimum number of distinct vertex colors induced by a majestic \(k\)-edge coloring is called the majestic chromatic number of \(G\) and denoted by \(\psi(G)\). Thus, \(\psi(G)\) is at least as large as the chromatic number \(\chi(G)\) of a graph \(G\). Majestic chromatic indexes and numbers are determined for several well-known classes of graphs. Furthermore, relationships among the three chromatic parameters \(\chi_m(G)\), \(\psi(G)\), and \(\chi(G)\) of a graph \(G\) are investigated.