Projective, affine, and abelian colorings of cubic graphs
Projective, affine, and abelian colorings of cubic graphs
复制标题
DOI：
10.1016/j.ejc.2007.11.029
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Král;Edita Mácajová;Ondrej Pangrác;A. Raspaud;Jean-Sébastien Sereni;M. Škoviera
中科院分区：
文献类型：
--
作者：
D. Král;Edita Mácajová;Ondrej Pangrác;A. Raspaud;Jean-Sébastien Sereni;M. Škoviera
本文提出了三次图的局部3-边染色的概念，它是通常的3-边染色的推广。我们允许无限数量的颜色，但要求在顶点处相遇的两条边的颜色总是确定相同的第三种颜色。局部3-边着色用部分Steiner三元系的点的着色来描述，使得在每个顶点处相遇的颜色形成该系统的三元系。在我们的研究中，一个重要的地方是由两个最小的非平凡Steiner三元系，Fano平面PG（2，2）和仿射平面AG（2，3）。对于i= 4，5和6，我们分别确定了Fano平面和仿射平面上i条线的某些配置Fi和Ai，并证明了一个定理：一个三次图允许Fi-染色当且仅当它允许Ai-染色.其中的后果是结果Holroyd和Škoviera [F. Holroyd，M.Škoviera，三次图的Steiner三元系着色，J. Combin。Theory Ser. B 91（2004）57-66]中提出了利用任意非平凡Steiner三元系S的点和块可以对任意无桥三次图的边进行着色。另一个结果是，每个无桥三次图都有一个适当的边染色的元素的任何阿贝尔群的阶至少为12，使周围的每个顶点的组元素的总和为0。我们还提出了几个关于三次图边染色的定理，并把它们与几个著名的定理联系起来。特别是，我们表明，无论是循环双覆盖猜想和Fulkerson猜想可以制定为一个着色问题的已知的几何配置-Desargues配置和Cremona-Richmond配置，分别。
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 Fiand Aiof i lines of the Fano plane and the affine plane, respectively, and prove a theorem saying that a cubic graph admits an Fi-coloring if and only if it admits an Ai-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 S. 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.