Facial entire colouring of plane graphs

详细信息    查看全文

• 作者：I. Fabrici ^{igor.fabrici@upjs.sk" class="auth_mail" title="E-mail the corresponding author} ; S. Jendrol&rsquo ; ; ^{stanislav.jendrol@upjs.sk" class="auth_mail" title="E-mail the corresponding author} ; M. Vrbjarová ; ^{michaela.vrbjarova@student.upjs.sk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Plane graph ; Entire colouring ; Facial colouring ; Edge&ndash ; face colouring
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：626-631
• 全文大小：415 K

文摘

Let 145bced19ae406ad6dad92ef70b26" title="Click to view the MathML source">G=(V,E,F)$G=(V,E,F)$ be a connected, loopless, and bridgeless plane graph, with vertex set V$V$, edge set E$E$, and face set F$F$. For X∈{V,E,F,V∪E,V∪F,E∪F,V∪E∪F}$X\in \{V,E,F,V\cup E,V\cup F,E\cup F,V\cup E\cup F\}$, two elements x$x$ and y$y$ of X$X$ are facially adjacent in G$G$ if they are incident, or they are adjacent vertices, or adjacent faces, or facially adjacent edges (i.e. edges that are consecutive on the boundary walk of a face of G$G$). A k$k$-colouring is facial with respect to X$X$ if there is a k$k$-colouring of elements of X$X$ such that facially adjacent elements of X$X$ receive different colours. We prove that: (i) Every plane graph 145bced19ae406ad6dad92ef70b26" title="Click to view the MathML source">G=(V,E,F)$G=(V,E,F)$ has a facial 8-colouring with respect to X=V∪E∪F$X=V\cup E\cup F$ (i.e. a facial entire 8-colouring). Moreover, there is plane graph requiring at least 7 colours in any such colouring. (ii) Every plane graph 145bced19ae406ad6dad92ef70b26" title="Click to view the MathML source">G=(V,E,F)$G=(V,E,F)$ has a facial 6-colouring with respect to X=E∪F$X=E\cup F$, in other words, a facial edge–face 6-colouring.