An Edge Bicoloring View of Edge Independence and Edge Domination

Abstract

A $red-bluecoloring$ 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 $colorframe$ $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$-$chromaticindex$ 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 $upperF-chromaticindex$ 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.