论文标题
2型平面图及以后的奇数着色
Odd coloring of 2-boundary planar graphs and beyond
论文作者
论文摘要
在本文中，我们介绍了2符号平面图的概念。如果图形在平面上有嵌入，则图是2符合条件的平面，以便所有顶点位于最多两个面的边界上，并且没有边缘。如果每个未分离的顶点都有某种颜色在其附近出现奇怪的次数，则图形的适当着色是奇怪的。 Petruševski和Škrekovski在2022年猜想每个平面图都构成了奇怪的5色。我们确认了这一猜想的2符号平面图。此外，我们提出了有关具有独立感兴趣的两条平面图的几个问题。
In this paper, we introduce the notion of 2-boundary planar graphs. A graph is 2-boundary planar if it has an embedding in the plane so that all vertices lie on the boundary of at most two faces and no edges are crossed. A proper coloring of a graph is odd if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. Petruševski and Škrekovski conjectured in 2022 that every planar graph admits an odd 5-coloring. We confirm this conjecture for 2-boundary planar graphs. Moreover, we present several questions regarding 2-boundary planar graphs that are of independent interest.
