The skew chromatic index of a graph |
| |
Authors: | Marsha F Foregger |
| |
Institution: | Bell Telephone Laboratories, Murray Hill, NJ 07974, U.S.A. |
| |
Abstract: | We define a skew edge coloring of a graph to be 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. We show that this concept is closely related to that of skew Room squares and use this relation to prove that s(G) is at most o(G) + 4. We also find better upper bounds for s(G) when G is cyclic, cubic, or bipartite. In particular we use a construction involving Latin squares to show that if G is complete bipartite of order 2n, s(G) is bounded above by roughly . |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|