Strong chromatic index of some cubic graphs

Question

Edit 2019 June 26 New computer evidence forces us to revise our guesses relating strong chromatic index and girth

Edit 2019 June 25 Some mistakes have been corrected. Question 2 has changed.

Edit 2019 August 28 There is now an answer (posted as such) to the question by Andersen et al. A new question now will take its place

Additional information Additional information is provided regarding small graphs with high strong chromatic index.

...

Definition (somewhat informal) A strong edge $k$ coloring of a cubic (3-regular) graph is a proper $k$ coloring of its edges so that for each edge, the four edges adjacent to it are colored differently. The strong chromatic index $\chi_S(G)$ of a cubic graph $G$ is the smallest number $k$ for which $G$ has a strong edge $k$ coloring.

Andersen, in 1, showed that if $G$ is a sub-cubic graph (a graph of max degree 3), then $\chi_S(G)\le 10$. In the same paper, he asks (the question is attributed to Faudree, Gyárfás, Schelp, and Tuza):

Andersen-Faudree-Gyárfás-Schelp-Tuza question, 1992 Is there is a constant $m$ such that if a cubic graph $G$ is such that the girth $g(G)$ of $G$ is at least $m$, then $\chi_S(G)=5$?

Edit 2019 August 28 The answer to this question is now known to be negative, see posted answer for proof.

This question is highly significant, as the truth of it would imply the truth of several notorious (cycle double cover, Berge-Fulkerson) graph theoretical conjectures for all (cubic) graphs of large enough girth.

Edit 2019 August 28 Since the question above is answered now in the negative (see posted answer), we make a new one:

Question (EGME-Jensen 2019) Is there is a constant $m$ such that if a cubic graph $G$ is such that the girth $g(G)$ of $G$ is at least $m$, then $\chi_S(G)=6$?

As a bit of background information to our question ahead, some (as yet very incomplete) computer investigations would seem to indicate that for bridgeless $G$:

Guess and estimates

1) if $g(G)\ge 5$ then $\chi_S(G)\le 7$*;

2) In order for $\chi_S(G)\le 6$ it is needed that $g(G)$ be at least 11**.

We now have

3) In order for $\chi_S(G)= 5$ it is needed that the number of edges in the $G$ be a multiple of 5.

*Regarding the first guess, it is worth noting that the clique number of the square graph of the line graph of the cubic graphs in question, - which determine the strong chromatic index - drops to 5, from greater than 5 in graphs of smaller girth.

** Regarding the second estimate, all graphs of girth 9 that have been tested have strong chromatic index at most 6. However, the first (3,10)-cage listed in [2] (a girth 10 graph) turned out to have strong chromatic index of 7 - the graph is called the Harries graph. The computation that determined this took several days on a standard laptop.

*** We have verified that the smallest known cubic graph of girth 17 listed in [2] does not have a strong edge 5 coloring, and that the smallest cubic graph of girth 18 in [2] has a strong edge 5 coloring.

We are currently trying to establish the strong chromatic index of several graphs of girth larger than 9 listed in [2], and we are also trying to establish whether the smallest cubic graph of girth 19 known and listed in [2] has a strong edge 5 coloring. We will update this post as information is further verified, or refuted - there is much testing that needs be done yet. However, we believe there is a firm basis for our main question (question 1) ahead. Before it, a bit more about graphs of small girth: almost all (bridgeless) graphs can be colored with 8 colors. The picture ahead shows the only exceptions to this with 18 or fewer vertices, with their colorings. The only one requiring ten colors is the fourth one in the list. We believe there aren't any more.

Before we pose our question, we need a definition.

Definition Let an $n$-prismatic graph be a cubic graph obtained by joining two disjoint circuits of order $n$ with a perfect matching.

Our first question is then:

Question 1 [main question] Let $G$ be prismatic of girth at least 4. Is the strong chromatic index of $G$ at most 8? Moreover, if the girth of $G$ is greater than 4, then, is the strong chromatic index of $G$ at most 7? We note that the prism with two triangles has strong chromatic index 9. As always in our posts, the intent of the question is to provide proof or provide a counterexample.

The nature of a possible proof of this is almost necessarily algorithmic. An inductive proof of the more general statement that bridgeless graphs of girth at least 4 have strong chromatic index at most 8 seems a bit out of reach at the moment. Indeed, in working with general graphs of girth 4 and finding subgraphs which are strong 8-critical, we have found over a thousand that are not isomorphic, and fairly large. Of course, there are a few that are small and that occur a lot more often.

In 1 a linear time algorithm to find a strong coloring with at most 10 colors is given. We would also like to know if:

Question 2 Is there a fast (linear time?) and simple algorithm to find a strong edge 9 coloring of a bridgeless cubic graph with 10 or more vertices?

1 Andersen, L. D., The strong chromatic index of a cubic graph is at most 10, Discrete Mathematics, 108 (1992) 231-252

[2] Royle, G. Cubic Cages, staffhome.ecm.uwa.edu.au/~00013890/remote/cages/index.html#data

Answer 1

The following paper provides a partial answer to our question 1 in the affirmative. It is an interesting read. Nonetheless, our question remains open in its full generality. Specifically, it shows that some prisms, some generalized Petersen graphs, have the strong chromatic indices we proposed.

[3] Yang, Z, and Wu, B., Strong chromatic index of the generalized Petersen graphs, Applied Mathematics and Computation 321 (2018) 431-441 https://www.sciencedirect.com/science/article/abs/pii/S0096300317307464

Answer 2

There is now an answer to the first question (Andersen et al.), which is quite surprising, as it looked rather difficult to settle. It is over 20 years old, and the answer came as a surprise during the Nordic Combinatorics Conference in Copenhagen at the beginning of August. The main argument was given by Andersen himself.

The answer is negative, which is shown by a counting argument pointed out by Lars D. Andersen, as follows.

Let $G=(V,E)$ be a cubic graph. For each edge $e$ let $N_e$ be the 'neighborhood' set that contains $e$ and the four edges adjacent to $e$ as elements. Assume that there exists a strong $5$-coloring $\varphi$ of $G$, that is, an edge coloring for which the edges in $N_e$ are all colored differently for all $e\in E.$ Let $c$ be any one of the five colors. Then the number of pairs $(e,e')$ with $e \in E,$ $e'\in N_e$ and $\varphi(e')=c$ is equal to $|E|,$ since for each $e$ there is precisely one $e'$ for which $(e,e')$ is such a pair. On the other hand, if we fix any $e'$ with $\varphi(e')=c,$ then there are exactly $5$ pairs $(e,e')$ with $e'\in N_e,$ indeed, one pair for each $e\in N_{e'}.$ This proves that if $G$ has a strong $5$-coloring, then the size $|E|$ of $G$ must be a multiple of $5.$

Now it is straightforward for any $g\geq 3$ to construct a cubic graph of girth at least $g$ that does not allow a strong $5$-coloring. Let $G$ be a cubic graph of girth at least $2g-2.$ If the size of $G$ is not a multiple of $5,$ then we are done, by Lars's argument. Otherwise, we choose a path $P$ of length $g-1$ in $G,$ which is possible, since the diameter is always at least half the girth. Subdivide the first and last edges of $P$ by new vertices $u$ and $v,$ respectively, and add a new edge $uv.$ Then the resulting graph is cubic of girth $g.$ Since its size is congruent to $3$ modulo $5,$ it has no strong $5$-coloring.