On Color Frames of Claws and Matchings

Abstract

A red-blue coloring of a graph $G$ is an edge coloring of $G$ in which every edge of $G$ is colored red or blue. Let $F$ be a connected graph of size $2$ or more with a red-blue coloring, at least one edge of each color, where some blue edge of $F$ is designated as the root of $F$. Such an edge-colored graph $F$ is called a color frame. 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$. The $F$-chromatic index ${\chi }_F^{\prime }(G)$ of $G$ is the minimum number of red edges in an $F$-coloring of $G$. A minimal $F$-coloring of $G$ is an $F$-coloring with the property that if any red edge of $G$ is re-colored 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 ${\chi }_F”(G)$ of $G$. In this paper, we study the two color frames $Y_1$ and $Y_2$ that result from the claw $K_{1,3}$, where $Y_1$ has exactly one red edge and $Y_2$ has exactly two red edges. For a graph $G$, let ${\alpha }^{\prime }(G)$ and $\alpha ”(G)$ denote the matching number and lower matching number of $G$, respectively. It is shown that if $T$ is a tree of order at least $4$ having no vertex of degree $2$, then ${\chi }_{Y_1}^{\prime }(T)=\alpha ”(T)$ while ${\chi }_{Y_2}^{\prime }(T)\le 3\alpha ”(T)$ and this upper bound is sharp. For a color frame $F$ of a claw, sharp bounds are established for ${\chi }_F”(G)$ in terms of the matching number and a generalized matching parameter of a graph $G$. Other results and questions are also presented.