Projective, affine, and abelian colorings of cubic graphs

Abstract: 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 and the affine plane . For , and 6 we identify certain configurations and of lines of the Fano plane and the affine plane, respectively, and prove a theorem saying that a cubic graph admits an -coloring if and only if it admits an -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 . 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. [Copyright &y& Elsevier]