Menu
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'(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'(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}'(T) = \alpha”(T) \) while \( \chi_{Y_2}'(T) \leq 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.