\((g,f)\)-factorization orthogonal to a star in graphs (Q1902277)

The author proves the existence of a factorization of a graph into factors which are orthogonal to a special subgraph of \(G\). Let \(G= (V, E)\) be a graph, \(H\) a spanning subgraph of \(G\), \(g(v)\) and \(f(v)\) integer functions defined on \(V\) with the property that \(g(v)\leq \deg_H(v)\leq f(v)\) for every vertex \(v\). Then \(H\) is called a \((g, f)\)-factor of \(G\). A factorization of \(G\) is a decomposition \(F= (F_1, F_2,\dots, F_m)\) of \(G\) into factors. A factorization \(F\) is orthogonal to a subgraph \(H\) of \(G\), if \(|E(H)\cap E(F_i)|= 1\) for all \(i\). Let \(G\) be an \((mg+ m- 1, mf- m+ 1)\)-graph. The main result of the paper establishes the existence of an \((f, g)\)-factorization \(F\) orthogonal to a given \(m\)-star \(H\) of \(G\). This result is the best possible with respect to the boundaries of the degree \(\deg(v)\) in \(G\).