Publication details
Projective, affine, and abelian colorings of cubic graphs
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Periodical |
| Magazine / Source | European Journal of Combinatorics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2007.11.029 |
| Description | 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, 5, and 6 we identify certain configurations F-i and A(i) of i lines of the Fano plane and the affine plane, respectively, and prove a theorem saying that a cubic graph admits an F-i-coloring if and only if it admits an A(i)-coloring. Among consequences of this is the result of Holroyd and Skoviera [F. Holroyd, M. Skoviera, Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Set. 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 S. |