Every graph with maximum degree at most four is (1¹,2¹⁹)-packing edge-colorable and (1²,2¹⁷)-packing edge-colorable
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.
- Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorable
- scientific article; zbMATH DE number 3851125 (Why is no real title available?)
- Maximum matchings in regular graphs
- On S-packing edge-colorings of cubic graphs
- On an estimate of the chromatic class of a \(p\)-graph
- On Representatives of Subsets
- Strong chromatic index of graphs with maximum degree four
- Strong edge-coloring of graphs with maximum degree 4 using 22 colors
- The strong chromatic index of \((3,\Delta)\)-bipartite graphs
This page was built for publication: Every graph with maximum degree at most four is \((1^1,2^{19})\)-packing edge-colorable and \((1^2,2^{17})\)-packing edge-colorable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7008161)
