Every graph with maximum degree at most four is \((1^1,2^{19})\)-packing edge-colorable and \((1^2,2^{17})\)-packing edge-colorable (Q7008161)

The authors consider edge colourings of graphs in which two disjoint sets \(A\) and \(B\) of colours are available. No colour may be used on two edges incident with the same vertex, as with standard (proper) edge colourings. But there is an additional restriction on the use of colours from set \(B\): no colour from set \(B\) may be used on two non-adjacent edges for which there is a third edge incident with both of them. A \((1^j,2^k)\)-packing edge-colouring is such a colouring in which there are \(j\) colours available in set \(A\) and \(k\) colours available in set \(B\). So when \(k=0\), this is just standard edge colouring.\N\NA special case of a conjecture of Erdős and Nešetřil posits that every graph with maximum degree at most four has a \((1^0,2^{20})\)-packing edge-colouring, and it is known that every such graph has a \((1^0,2^{21})\)-packing edge-colouring [\textit{M. Huang} et al., Electron. J. Comb. 25, No. 3, Research Paper P3.31, 24 p. (2018; Zbl 1395.05057)]. In the present paper, the authors show that every such graph has both a \((1^1,2^{19})\)-packing edge-colouring and a \((1^2,2^{17})\)-packing edge-colouring. Most of the effort in both proofs goes into proving that a minimum counterexample must be \(4\)-regular and have no short cycles. The proofs are well written.\N\NVizing's theorem implies that every graph with maximum degree at most four has a \((1^5,2^0)\)-packing edge-colouring. As the authors point out, the notion of \((1^j,2^k)\)-packing edge-colouring `interpolates' between the problem considered by Erdös and Nesẽt\~ril and standard edge colouring, and some simple arguments give upper bounds on the values of \(k\) for which there are \((1^j,2^k)\)-packing edge-colourings when \(j=3\) or \(4\). The authors hint at the interesting problem of determining whether these bounds are best possible.