Null and non-rainbow colorings of projective plane and sphere triangulations

详细信息    查看全文

• 作者：Jorge L. Arocha^a ; ^{arocha@matem.unam.mx" class="auth_mail" title="E-mail the corresponding author} ; Amanda Montejano^b ; ^{amandamontejano@ciencias.unam.mx" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Anti-Ramsey theory ; Non-rainbow colorings ; Sphere and projective plane triangulations
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 September 2016
• 年：2016
• 卷：210
• 期：Complete
• 页码：195-199
• 全文大小：385 K

文摘

By considering graphs as topological spaces we introduce, at the level of homology, the notion of a null coloring, which provides new information on the task of clarifying the structure of cycles in a graph. We prove that for any graph G$G$ a maximal null coloring f$f$ is such that the quotient graph G/f$G/f$ is acyclic. As an application, for maximal planar graphs (sphere triangulations) of order n≥4$n\ge 4$, we prove that a vertex-coloring containing no rainbow faces uses at most $\lfloor \frac{2n-1}{3}\rfloor$ colors, and this is best possible. For maximal graphs embedded on the projective plane we obtain the analogous best bound $\lfloor \frac{2n+1}{3}\rfloor$.