论文标题
亚地铁平面图的精确方形着色
Exact square coloring of subcubic planar graphs
论文作者
论文摘要
我们研究了确切的平方色平面图的确切平方形数。图G的精确正方形着色是顶点颜色的，其中距离的任何两个顶点正好获得2个不同的颜色。 G的颜色中使用的最少数量的颜色是其确切的正方形色编号，表示$χ^{\ sharp 2}（g）$。该概念与其他类型的基于距离的着色以及注入性着色有关。确实，对于无三角形的图，精确的正方形着色和注入性着色一致。我们证明了平面图的特殊子类的紧密界限：亚立比式平面平面图和亚立管K 4毫无用处的图最多具有精确的正方形色数。然后，我们将注意力转向富勒烯图，这些图形是带有5和6的立方平面图5和6的立方平面图。 Hahn，Raspaud和Wang（所有亚地铁平面图都是可提录的5色图），我们证明，富勒烯图的任何诱导的子图最多都具有精确的正方形色数。
We study the exact square chromatic number of subcubic planar graphs. An exact square coloring of a graph G is a vertex-coloring in which any two vertices at distance exactly 2 receive distinct colors. The smallest number of colors used in such a coloring of G is its exact square chromatic number, denoted $χ^{\sharp 2}(G)$. This notion is related to other types of distance-based colorings, as well as to injective coloring. Indeed, for triangle-free graphs, exact square coloring and injective coloring coincide. We prove tight bounds on special subclasses of planar graphs: subcubic bipartite planar graphs and subcubic K 4-minor-free graphs have exact square chromatic number at most 4. We then turn our attention to the class of fullerene graphs, which are cubic planar graphs with face sizes 5 and 6. We characterize fullerene graphs with exact square chromatic number 3. Furthermore, supporting a conjecture of Chen, Hahn, Raspaud and Wang (that all subcubic planar graphs are injectively 5-colorable) we prove that any induced subgraph of a fullerene graph has exact square chromatic number at most 5. This is done by first proving that a minimum counterexample has to be on at most 80 vertices and then computationally verifying the claim for all such graphs.
