Abstract

A skew edge coloring of a graph G is defined as a set of two edge colorings such that no two edges are assigned the same unordered pair of colors. The skew chromatic index s(G) is the minimum number of colors required for a skew edge coloring of G. In this article, we develop an algorithm for skew edge coloring of 2-rooted sibling trees and cyclic snake graphs. The minimum number of colors k which is known as the skew chromatic index is determined depending upon the number of edges of G. Furthermore, it is proved that the bound on the skew chromatic index s(G) ≥ max{Δ(G); k(|E(G)|)} is sharp for the family of graphs considered for skew edge coloring.

Keywords and Phrases

Skew edge coloring, skew chromatic index, 2-rooted sibling tree, cyclic snake graphs, NP-complete.

A.M.S. subject classification

05C15.

.....