论文标题
改善了一些面部约束的颜色的界限
Improved bounds for some facially constrained colorings
论文作者
论文摘要
$ 2 $ - 边缘连接的平面图的面部 - 偏边彩色是一个面部偏好的边缘色，其中每张脸部都以零或奇数边缘的形式入射。 $ 2 $连接的平面图的面部范围顶点颜色是一种面部构图，每个脸部都以零或每种颜色的奇数顶点入射。 CZAP和Jendroľ（在平面图的面部色彩中：调查，离散数学340（2017），2691---2703）猜想，两种颜色都可以$ 10 $颜色。我们向这两个猜想提出了一个无限的反例。 面部$（p_ {k}，p _ {\ ell}）$ - 平面图$ g $的蠕虫着色是顶点的颜色，以至于$ g $不包含彩虹面部$ k $ - $ k $ - 没有单色面部面部面部$ \ ell $ - Czap, Jendroľ and Valiska (in WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017), 353--368), proved that for any integer $n\ge 12$ there exists a connected plane graph on $n$ vertices, with maximum degree at least $6$, having no facial $(P_{3},P_{3})$-WORM coloring.他们还询问是否存在具有相同属性的最高度$ 4 $的图表。我们证明，对于任何整数$ n \ ge 18 $，都存在一个连接的平面图，最高度$ 4 $，没有面部$（p_ {3}，p_ {3}），p_ {3}）$ - 蠕虫着色。
A facial-parity edge-coloring of a $2$-edge-connected plane graph is a facially-proper edge-coloring in which every face is incident with zero or an odd number of edges of each color. A facial-parity vertex-coloring of a $2$-connected plane graph is a facially-proper vertex-coloring in which every face is incident with zero or an odd number of vertices of each color. Czap and Jendroľ (in Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017), 2691--2703), conjectured that $10$ colors suffice in both colorings. We present an infinite family of counterexamples to both conjectures. A facial $(P_{k}, P_{\ell})$-WORM coloring of a plane graph $G$ is a coloring of the vertices such that $G$ contains no rainbow facial $k$-path and no monochromatic facial $\ell$-path. Czap, Jendroľ and Valiska (in WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017), 353--368), proved that for any integer $n\ge 12$ there exists a connected plane graph on $n$ vertices, with maximum degree at least $6$, having no facial $(P_{3},P_{3})$-WORM coloring. They also asked if there exists a graph with maximum degree $4$ having the same property. We prove that for any integer $n\ge 18$, there exists a connected plane graph, with maximum degree $4$, with no facial $(P_{3},P_{3})$-WORM coloring.
