Definition(somewhat informal) Astrong edge $ k$ coloringof a cubic (3-regular) graph is a proper $ k$ coloring of its edges so that any edge together the four edges adjacent to it are colored with 5 colors. Thestrong chromatic index$ \chi_S(G)$ of a cubic graph $ G$ is the smallest number $ k$ such that $ 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 proposed the following:

Conjecture[Andersen, 1992] There is a constant $ g$ such that if a cubic graph $ G$ is such that girth $ \gamma(G)\ge g$ , then $ \chi_S(G)=5$ .

This conjecture is highly significant, as the truth of it would imply the truth of several notorious graph theoretical conjectures for all (cubic) graphs of large enough girth.

As a bit of background information to our question ahead, some (as yet very incomplete) computer investigations would seem to indicate that if $ G$ is bridgeless (and of girth at least 4, although we are not sure this is really needed), then $ \chi_S(G)\le 8$ , and also, if $ \gamma(G)\ge 5$ then $ \chi_S(G)\le 7$ , and if $ \gamma(G)\ge 9$ then $ \chi_S(G)\le 6$ . Finally, we have verified that the (3,17)-cage listed in [2] does not have a strong edge 5 coloring, and that the (3,18)-cage 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 (3,19)-cage in [2] has a strong edge 5 coloring. And we should probably look at a lot more graphs with small girth. We will update this post as this information is further verified, or refuted – our computations are geared at the moment towards graphs with girth higher than 4. We need to do a lot more checking on graphs with girth 3 and 4 and we acknowledge that this is lacking. There is only so much compute time available … however, we believe there is a firm basis for our main question (question 1) ahead.

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. Then the strong chromatic index of $ G$ is at most 8. Moreover, if the girth of $ G$ is greater than 4, then the strong chromatic index of $ G$ is at most 7. As always in our posts, prove of 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 8 coloring of a bridgeless cubic graph?

[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