一个关于平面图的K-(2,1)-全可选性的结果

设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in E(G)$时, $|c(u)-c(v)|\geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|\geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|\geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,x\in V(G)\cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$\Delta(G)\geq 11$的平面图, 则$C_{2,1}^{T}(G)\leq\Delta+4$.     

最大度至多为6的平面图的L(2,1)-标号

令Δ(G),g(G)和λ(G)分别为图G的最大度,围长,和L(2,1)-标号数.证明了若G是Δ(G)≤6和g(G)≥5的平面图,则λ(G)≤Δ(G)+13.进而关于Δ(G)≤6和g(G)≥5的平面图G,这个界要比先前的结果好.     

不含4,5,6-圈的平面图的L(p,q)-标号

证明了若G为不含4,5,6-圈的平面图,则λp,q(G)≤(2q- 1)Δ(G)+6p+6q-6.这一结果暗含着对于△(G)≥12且不含4,5,6-圈的平面图G,x(G2)≤[3Δ(G)/2]+1成立.因此对于这样一类图部分地证实了Wegner猜想.     

不含4-9圈的平面图的L(p,q)-标号

令p≥q是两个正整数.用△(G)和λp,q(G)分别记平面图G的最大度和L(p,q)-标号数.文章证明了若G为不含i-圈,4≤i≤9的平面图,则λp,q(G)≤(2q- 1)Δ(G)+8p-4.这一结果推出x (G2)≤△(G)+5.因此对于这样一类图部分地证实了Wegner的猜想[2].     

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.     

几类特殊图的(2,1)-全标号

研究了与频道分配有关的一种染色-(p,1)-全标号.通过在一个顶点粘结不同的简单图构造了几类有趣图,根据所构造图的特征,利用穷染法,给出了一种标号方法,得到了平凡和非平凡叶子图Gm,4、风车图K3t和图Dm,n的(2,1)-全标号数.(p,1)-全标号是对图的全染色的一种推广.     

外平面图的L(2,1)-标号

外平面图是没有子图为K₄或K_2,3的剖分的图。设G为一个外平面图,本文证明了G的L(2,1)标号数λ(G)≤Δ(G)+9。     

既不含4-圈又不含6-圈的平面图的非正常染色

设d₁, d₂,..., d_k是k个非负整数. 若图G=(V,E)的顶点集V能被剖分成k个子集V₁, V₂,...,V_k, 使得对任意的i=1, 2,..., k, V_i的点导出子图G[V_i] 的最大度至多为d_i, 则称图G是(d₁, d₂,...,d_k)-可染的. 本文证明既不含4-圈又不含6-圈的平面图是(3, 0, 0)-和(1, 1, 0)-可染的.     

最大度为3的树的L(2,1)-标号数的一个刻画

图G的一个L(2,1)-标号是对G顶点集合的一个非负整数分配,使得其中相邻的点取得的整数差值至少为2并且距离为2的点取得不同的整数.L(2,1)-标号数就是所有这样的标号分配中最小的标号跨度值.Griggs和Yeh的[Labelling graphs with a condition at distance 2,SIAM J.Discrete Math.,1992,5:586-595]已经证明了,一棵树的L(2,1)-标号数不是△就是△+1.对于最大度为3的树的L(2,1)-标号数,本文给出了一个完全的刻画.     

不含5-圈的平面图的无圈边着色

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.     

Planar graphs without 5-cycles or without 6-cycles

Let G be a planar graph without 5-cycles or without 6-cycles. In this paper, we prove that if G is connected and δ(G)≥2, then there exists an edge xy∈E(G) such that d(x)+d(y)≤9, or there is a 2-alternating cycle. By using the above result, we obtain that (1) its linear 2-arboricity , (2) its list total chromatic number is Δ(G)+1 if Δ(G)≥8, and (3) its list edge chromatic number is Δ(G) if Δ(G)≥8.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$     

Acyclic 5-choosability of planar graphs without 4-cycles

A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k-choosable. In this paper we prove that every planar graph without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281-300], which says that planar graphs of girth at least 5 are acyclically 5-choosable.     

Acyclic 5-choosability of planar graphs without 4-cycles

The conjecture on the acyclic 5-choosability of planar graphs (Borodin et al., 2002) as yet has been verified only for several restricted classes of graphs: those of girth at least 5 (Montassier, Ochem, and Raspaud, 2006), without 4- and 5-cycles or without 4- and 6-cycles (Montassier, Raspaud, and Wang, 2007), with neither 4-cycles nor chordal 6-cycles (Zhang and Xu, 2009), with neither 4- cycles nor two 3-cycles at distance less than 3 (Chen and Wang, 2008), and with neither 4-cycles nor intersecting 3-cycles (Chen and Raspaud, 2010). Wang and Chen (2009) proved that the planar graphs without 4-cycles are acyclically 6-choosable. We prove that a planar graph without 4-cycles is acyclically 5-choosable, which is a common strengthening of all above-mentioned results.     

DP-4-colorability of planar graphs without intersecting 5-cycles

DP-coloring of graphs as a generalization of list coloring was introduced by Dvo?ák and Postle (2018). In this paper, we show that every planar graph without intersecting 5-cycles is DP-4-colorable, which improves the result of Hu and Wu (2017), who proved that every planar graph without intersecting 5-cycles is 4-choosable, and the results of Kim and Ozeki (2018).