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

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

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

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

...

Definition(somewhat informal) Astrong edge $k$ coloringof 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. Thestrong 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, 1992Is 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 28The 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 28Since 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 estimates1) 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 have3) 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.

DefinitionLet an$n$-prismaticgraph 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 2Is 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