Projective, affine, and abelian colorings of cubic graphs

We develop an idea of a local 3-edge-coloring   of a cubic graph, a generalization of the usual 3-edge-coloring. We allow for an unlimited number of colors but require that the colors of two edges meeting at a vertex always determine the same third color. Local 3-edge-colorings are described in terms of colorings by points of a partial Steiner triple system such that the colors meeting at each vertex form a triple of the system. An important place in our investigation is held by the two smallest non-trivial Steiner triple systems, the Fano plane PG(2,2) and the affine plane AG(2,3). For i=4,5i=4,5, and 6 we identify certain configurations FiFi and AiAi of ii lines of the Fano plane and the affine plane, respectively, and prove a theorem saying that a cubic graph admits an FiFi-coloring if and only if it admits an AiAi-coloring.Among consequences of this is the result of Holroyd and Škoviera [F. Holroyd, M. Škoviera, Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Ser. B 91 (2004) 57–66] that the edges of every bridgeless cubic graph can be colored by using points and blocks of any non-trivial Steiner triple system SS. Another consequence is that every bridgeless cubic graph has a proper edge-coloring by elements of any abelian group of order at least 12 such that around each vertex the group elements sum to 0.We also propose several conjectures concerning edge-coloring of cubic graphs and relate them to several well-known conjectures. In particular, we show that both the Cycle Double Cover Conjecture and the Fulkerson Conjecture can be formulated as a coloring problem in terms of known geometric configurations — the Desargues configuration and the Cremona–Richmond configuration, respectively.