Facial list colourings of plane graphs

详细信息    查看全文

• 作者：Igor Fabrici^a ; ^{igor.fabrici@upjs.sk" class="auth_mail" title="E-mail the corresponding author} ; Stanislav Jendrol&rsquo ; ^a ; ^{stanislav.jendrol@upjs.sk" class="auth_mail" title="E-mail the corresponding author} ; Margit Voigt^b ; ^{mvoigt@informatik.htw-dresden.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：List colouring ; Facial colouring ; Total colouring ; Entire colouring ; Plane graph
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 November 2016
• 年：2016
• 卷：339
• 期：11
• 页码：2826-2831
• 全文大小：393 K

文摘

Let G=(V,E,F)$G=(V,E,F)$ be a connected 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 distinct elements of X$X$ are facially adjacent in G$G$ if they are incident elements, adjacent vertices, adjacent faces, or facially adjacent edges (edges that are consecutive on the boundary walk of a face of G$G$). A list k$k$-colouring is facial with respect to X$X$ if there is a list k$k$-colouring of elements of X$X$ such that facially adjacent elements of X$X$ receive different colours. We prove that every plane graph G=(V,E,F)$G=(V,E,F)$ has a facial list 4-colouring with respect to X=E$X=E$, a facial list 6-colouring with respect to X∈{V∪E,E∪F}$X\in \{V\cup E,E\cup F\}$, and a facial list 8-colouring with respect to X=V∪E∪F$X=V\cup E\cup F$. For plane triangulations, each of these results is improved by one and it is tight. These results complete the theorem of Thomassen that every plane graph has a (facial) list 5-colouring with respect to X∈{V,F}$X\in \{V,F\}$ and the theorem of Wang and Lih that every simple plane graph has a (facial) list 7-colouring with respect to X=V∪F$X=V\cup F$.