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 \). For integers \( k \) and \( m \) with \( 1 \leq k < m \) and \( m \geq 3 \), let \( S_{k,m} \) be the color frame of the star \( K_{1,m} \) of size \( m \) such that \( S_{k,m} \) has exactly \( k \) red edges and \( m-k \) blue edges. For a positive integer \( k \), a set \( X \) of edges of a graph \( G \) is a \( \Delta_k \)-set if \( \Delta(G[X]) = k \), where \( G[X] \) is the subgraph of \( G \) induced by \( X \). The maximum size of a \( \Delta_k \)-set in \( G \) is referred to as the \( k \)-matching number of \( G \) and is denoted by \( a_k'(G) \). A \( \Delta_k \)-set \( X \) is maximal if \( X \cup \{e\} \) is not a \( \Delta_k \)-set for every \( e \in E(G) – X \). The minimum size of a maximal \( \Delta_k \)-set of \( G \) is the lower \( k \)-matching number of \( G \) and is denoted by \( a_k''(G) \). In this paper, we consider \( S_{k,m} \)-colorings of a graph and study relations between \( S_{k,m} \)-colorings and \( \Delta_k \)-sets in graphs. Bounds are established for the \( S_{k,m} \)-chromatic indexes \( \chi_{S_{k,m}}'(G) \) and \( \chi_{S_{k,m}}''(G) \) of a graph \( G \) in terms of the \( k \)-matching numbers \( a_k'(G) \) and \( a_k''(G) \) of the graph. Other results and questions are also presented.