An Edge Bicoloring View of Edge Independence and Edge Domination

摘要

A red-blue coloring of a graph G is an edge coloring of G in which every edge is colored red or blue. For a connected graph H of size at least 2, a color frame F of H is obtained from a red-blue coloring of H having at least one edge of each color and in which a blue edge is designated as the root edge. An F-coloring of a graph G is a red-blue coloring of G in which every blue edge of G is the root edge of a copy of F in G and the F-chromatic index of G is the minimum number of red edges in an F-coloring of G. An F-coloring of G is minimal if whenever any red edge of G is changed to blue, then the resulting red-blue coloring of G is not an F-coloring of G. The maximum number of red edges in a minimal F-coloring of G is the upper F-chromatic index of G. In this paper, we investigate F-colorings and F-chromatic indexes of graphs for all color frames F of paths of orders 3 and 4.