Injective coloring of planar graphs
Injective coloring of planar graphs
复制标题
DOI：
10.1016/j.tcs.2021.01.007
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Y. Bu;Chentao Qi;Junlei Zhu;Ting Xu
中科院分区：
文献类型：
--
作者：
Y. Bu;Chentao Qi;Junlei Zhu;Ting Xu
图G的一个单射k染色是一个映射f: V (G)→{1,2，…，k}，使得对于任意两个顶点v1， v2∈V (G)，如果N (v1)∩N (v2)≠∅,f (v1)≠f （v2）。图G的内射色数，用χ i (G)表示，是使G具有内射k着色的最小整数k。本文证明了对于Halin图G， χ i (G)≤Δ (G)+ 2。如果Δ (G)≥6,χ i (G)≤Δ (G)+ 1。此外，我们还证明了对于不相交4环的无三角形平面图G，当Δ (G)≥20时，χ i (G)≤Δ (G)+ 6。
An injective k-coloring of a graph G is a mapping f: V (G)→{1, 2,…, k} such that for any two vertices v 1, v 2∈ V (G), f (v 1)≠ f (v 2) if N (v 1)∩ N (v 2)≠∅. The injective chromatic number of a graph G, denoted by χ i (G), is the smallest integer k such that G has an injective k-coloring. In this paper, we prove that for a Halin graph G, χ i (G)≤ Δ (G)+ 2. Moreover, χ i (G)≤ Δ (G)+ 1 if Δ (G)≥ 6. Also, we show that for a triangle-free planar graph G without intersecting 4-cycles, χ i (G)≤ Δ (G)+ 6 if Δ (G)≥ 20.