On Color Frames of Stars and Generalized Matching Numbers

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$. For integers $k$ and $m$ with $1\le k<m$ and $m\ge 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 ${\mathrm{\Delta }}_k$-set if $\mathrm{\Delta }(G[X])=k$, where $G[X]$ is the subgraph of $G$ induced by $X$. The maximum size of a ${\mathrm{\Delta }}_k$-set in $G$ is referred to as the $k$-matching number of $G$ and is denoted by $a_k^{\prime }(G)$. A ${\mathrm{\Delta }}_k$-set $X$ is maximal if $X\cup \{e\}$ is not a ${\mathrm{\Delta }}_k$-set for every $e\in E(G)–X$. The minimum size of a maximal ${\mathrm{\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 ${\mathrm{\Delta }}_k$-sets in graphs. Bounds are established for the $S_{k,m}$-chromatic indexes ${\chi }_{S_{k,m}}^{\prime }(G)$ and ${\chi }_{S_{k,m}}^{″}(G)$ of a graph $G$ in terms of the $k$-matching numbers $a_k^{\prime }(G)$ and $a_k^{″}(G)$ of the graph. Other results and questions are also presented.