Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs (Q2142635): Difference between revisions

For a graph \(G\) and a family \(\mathcal{H}\) of subgraphs of \(G\), we say a (not necessarily proper) colouring of the edges of \(G\) is \(\mathcal{H}\)-polychromatic if every graph in \(\mathcal{H}\) has edges of every colour used in the colouring of \(G\). The largest possible number of colourings in an \(\mathcal{H}\)-polychromatic colouring of \(G\) is called the \(\mathcal{H}\)-polychromatic number of \(G\) and is denoted by poly\(_{\mathcal{H}}(G)\). We consider the case where \(G\) is a complete graph on \(n\) vertices and abuse notation by writing poly\(_{\mathcal H}(n)\) for poly\(_{\mathcal H}(K_{n})\). As by Ramsey's theorem, if the graphs in \(\mathcal{H}\) were of bounded size we would get poly\(_{\mathcal H}(n)\)=1, we should only look at cases where the graphs in \(\mathcal{H}\) increase in size with \(n\). In [\textit{M. Axenovich} et al., J. Graph Theory 87, No. 4, 660--671 (2018; Zbl 1386.05051)] the value of poly\(_{\mathcal{H}}(n)\) is determined when \(\mathcal{H}\) is the set of perfect matchings (\(n\) even) and is approximated to within a small additive constant when \(\mathcal{H}\) is the set of 2-regular graphs or \(\mathcal{H}\) is the set of Hamilton cycles. The paper under review deals with the cases where (for a fixed integer \(q\)) \(\mathcal{H}\) is the set of all matchings covering \(n-q\) vertices, all \((n-q)\) cycles and all 2-regular graphs on at least \(n-q\) vertices. In all cases the exact answer is obtained. Note that for \(q=0\) the results confirm and extend those of Axenovich et al. The optimal colourings are based on certain orderings. There are links with extensions of results on Ramsey numbers for cycles in a graph. A conjecture more general than most of the results in the paper is also made.