2022 GVSU Summer Mathematics REU Project

The following is a description of Dr. Michael Santana's project for the 2022 GVSU Summer Mathematics REU on Packing-Edge Colorings.

Project Description and Background

Proper Edge-Colorings

An edge-coloring of a graph is a function in which every edge of the graph is assigned a label, that we call a color. An edge-coloring is said to be proper if incident edges always receive different colors. Every graph has a proper edge-coloring by simply assigning each edge a unique color. Therefore, the goal for each graph is determine the minimum number of colors needed in a proper edge-coloring of that graph; this minimum number of colors is called the chromatic index of that particular graph.

In the 1960's, Vizing [V] and independently later Gupta [G], showed that if Δ denotes the maximum degree of a graph, then the chromatic index of that graph always at most Δ + 1. Since it easy to see that the chromatic index of a graph is always at least Δ, this reduces the chromatic index of a graph to one of two possibilities. In spite of this reduction however, it was shown in the early 1980's that determining exactly which of these two options is the correct chromatic index of a given graph is NP-complete [H].

An example of a proper edge-coloring using three colors, which is the best possible for this particular graph. This can also be called a (1³, 2⁰)-packing edge-coloring as we will see later.

An example of a strong edge-coloring using nine colors, which is the best possible for this particular graph. This can also be called (1⁰, 2⁹)-packing edge-coloring as we will see later.

Strong Edge-Colorings

Also in the 1960's, Fouquet and Jolivet [FJ] introduced a new type of edge-coloring known as strong edge-coloring in which edges that receive the same color must be further apart than in a proper edge-coloring. More precisely in a strong edge-coloring, if two edges receive the same color, then they cannot be incident to each other nor can they be incident to a common edge. As with proper edge-colorings, assigning each edge of a graph a unique color easily produces a strong edge-coloring. Therefore, the question of interest is to determine the minimum number of colors needed in a strong edge-coloring of a particular graph, which is called the strong chromatic index. Erdős and Nešetřil [EN] conjectured that if a graph has maximum degree equal to Δ , then the strong chromatic index of that graph should be at most (5/4)Δ² if Δ is even, and at most (5/4)Δ² - (1/2)Δ + (1/4) if Δ is odd. This conjecture has only been verified for Δ at most three (shown in [A] and independently [HQT]). For graphs in which Δ is large, it is only known that at most 1.835 Δ² colors suffices. Therefore, there is still a significant amount of work to be done in the area of strong edge-colorings, and as a result, many other coloring parameters have been considered in attempts to make progress on strong edge-colorings.

Packing Edge-Colorings

Momentarily returning to proper edge-colorings, one simple observation is that when focusing solely on a collection of edges colored with the same color, these edges form what is called a matching in the underlying graph (i.e., these are edges that do not share any endpoints with each other). Consequently, another way to denote a proper edge-coloring is as a decomposition of the edge set of a graph into matchings. In a similar manner, one can denote a strong edge-coloring as a decomposition of the edge set of a graph into induced matchings (i.e., these are collections of edges such that no other edge in the graph has both of its endpoints amongst these edges). Therefore, a natural intermediate step between proper and strong edge-colorings is to attempt to decompose the edge-set of a graph into matchings, say k of them in total, and require j of these matchings (so 0 ≤ j ≤ k) to be induced matchings. Such a decomposition is called a (1^{k - j}, 2 ^j)-packing edge-coloring. Note that when j = 0, this is equivalent to proper edge-coloring, and when j = k, it is equivalent to strong edge-coloring.

An example of a (1¹, 2⁶)-packing edge-coloring of this particular graph where the six non-red colors are required to form induced matchings, but edges colored red only need to form a matching. It is worth convincing yourself that there is no (1¹, 2⁵)-packing edge-coloring of this graph.

An example of a (1², 2³)-packing edge-coloring of this particular graph, where the three non-red and non-blue colors are required to form induced matchings, but the edges colored red and the edges colored blue only need to form a matching. It is worth convincing yourself that there is no (1², 2²)-packing edge-coloring of this graph.

Project Goal

Motivated by a conjecture from [GT], the authors in [HLL] recently posed several conjectures of their own regarding packing edge-colorings of graph with maximum degree at most three. One of these conjectures has recently been resolved in [LSS], with the remaining conjectures still open. In this proposed project, students will explore this new area of edge-colorings, in particular as it pertains to graphs with maximum degree four as there is no known work for such graphs. This will allow students to the opportunity to produce new results as well as their own conjectures in this area.

Desirable Experiences for Applicants

Applicants for this project should have successfully taken an introduction to proofs course and have some familiarity with graph theory and graph colorings (a specific course in graph theory is preferred, but not necessary). In addition, applicants should have a desire (not just willingness) to work with others, and a positive attitude towards failing (I once apologized to my amazingly, successful PhD advisor after not proving a result in the span of several months, and he told me words I hope to never forget "Do not worry. This is my life. I try and I fail.").

How to Apply

For information on the REU, how to apply, etc., check out the main website for the REU: https://www.gvsu.edu/mathreu/. If you have questions about the application process or any other logistical questions regarding the REU, contact the REU email address at: mathreu [at] gvsu [dot] edu. If you have questions about this specific project, feel free to contact me via email: santanmi [at] gvsu [dot] edu.

References

[A] L. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math. 108 (1992) no. 1-3, 231-252.

[EN] P. Erdős and J. Nešetřil, Irregularities of partitions, Ed. G. Halász and V.T. Sós, (1989) 162-163.

[FJ] J. Fouquet and J. Jolivet, Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin. 16A (1983) 141-150.

[GT] N. Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019) 63-75.

[G] R. P. Gupta, Studies in the Theories of Graphs, Ph.D. thesis, Tata Institute, Bombay, 1967.

[HLL] H. Hocquard, D. Lajou, and B. Lužar, Between proper and strong edge-colorings of subcuic graphs, submitted.

[HQT] P. Horák, H. Qing, and W. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993) no. 2, 151-160.

[H] I. Hoyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) no. 4, 718-720.

[LSS] X. Liu, M. Santana, and T. Short, (1, 2⁷)-packing edge-colorings of subcubic graphs, Submitted.

[V] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964) 25-30.