Every graph with maximum degree at most four is (11,219)-packing edge-colorable and (12,217)-packing edge-colorable

Henderson, Cicely; Kennedy, Camille; Santana, Michael

doi:10.2140/involve.2025.18.261

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

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

Cicely Henderson, Camille Kennedy and Michael Santana

Vol. 18 (2025), No. 2, 261–282

DOI: 10.2140/involve.2025.18.261

Abstract

A $(1^{j}, 2^{k})$ -packing edge-coloring of a graph $G$ is an assignment of the colors ${1_{1}, 1_{2}, \dots, 1_{j}}$ and ${2_{1}, 2_{2}, \dots, 2_{k}}$ to the edges of $G$ such that any two edges that receive the same color are not incident to each other, and furthermore, if two edges are both colored $2_{i}$ for the same $i$ , where $1 \leq i \leq k$ , there cannot be a third edge incident to both. Note that when $k = 0$ , this notion is equivalent to a proper $j$ -edge-coloring, and when $j = 0$ this is equivalent to a strong $k$ -edge-coloring. In 1985, Erdős and Nešetřil posed a conjecture regarding strong edge-colorings of graphs based on their maximum degree $Δ$ that has been proven for $Δ \leq 3$ . In the language of packing edge-colorings, this conjecture posits that every graph with $Δ \leq 4$ has a $(1^{0}, 2^{20})$ -packing edge-coloring. It was recently shown that every graph with $Δ \leq 4$ has a $(1^{0}, 2^{21})$ -packing edge-coloring. In this paper, we approach this conjecture from a different direction by showing that every graph $G$ with $Δ \leq 4$ has a $(1^{1}, 2^{19})$ -packing edge-coloring. Additionally, we show that every graph $G$ with $Δ \leq 4$ has a $(1^{2}, 2^{17})$ -packing edge-coloring.

Keywords

edge-coloring, maximum degree

Mathematical Subject Classification

Primary: 05C15

Secondary: 05C70

Milestones

Received: 5 April 2023

Revised: 26 September 2023

Accepted: 27 September 2023

Published: 26 February 2025

Communicated by Ronald Gould

Authors

Cicely Henderson
Department of Combinatorics and Optimization University of Waterloo Waterloo, ON Canada

Camille Kennedy
Department of Mathematics Northwestern University Evanston, IL United States

Michael Santana
Department of Mathematics Grand Valley State University Allendale, MI United States

Vol. 18, No. 2, 2025