1-平面图的线性荫度

图G的边分解是指将G分解成子图G₁,G₂,…,G_m,使得E(G)=E(G₁)∪…∪E(G_m),且对任意i≠j有E(G_i)∩E(G_j)=?.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文利用权转移方法证明了Δ(G)≥25的1-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度.     

围长至少为4的平面图的邻点可区别边色数

图G的邻点可区别边染色是G的正常边染色,使得每一对相邻顶点有不同的颜色集合．G的邻点可区别边色数X＇a（G）是使得G有一个k-邻点可区别边染色的最小正整数七．本文证明了：若G是围长至少为4且最大度至少为6的平面图,则X＇a（G）≤△＋2．     

平面图4-可选的一个局部条件

给定图G的一个k-色列表L,若存在G的一个正常染色c且满足c(v)∈L(v),则称G是L-列表可染的.若对任意k-色列表L, G都是L-列表可染的,则称G是k-可选的.本文给出平面图4-可选的一个局部条件,即若平面图G的每个点不同时与3-、4-、5-和6-圈相关联,则G是4-可选的.     

IC-平面图的线性荫度

图G的边分解是指将G分解成子图G₁,G₂,...,G_m,使得E(G)-E(G₁)∪…∪.E(G_m),且对任意i≠j,有E(G_i)∩E(G_j)=?.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文证明了Δ(G)≥15的IC-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度.     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

图带宽和与其对偶超图带宽和的关系

设H=（E1,E2,…,Em）是集合X上的一个超图,一个1-1映射f:X→{1,2,…,|X|}称为H的一个标号,对H的任一标号f,BS（H,f）=∑(E∈H)max{|f(u)-f(v)|;u,v∈E}称为超图H的关于标号f的带宽和BS(H)=min{BS(H,f)|f是超图H的标号|}称为H的带宽和．论文研究图带宽和与其对偶超图的带宽和这两个参数间的关系．     

平面图点荫度的一个局部条件

图G的点荫度va(G)是指V(G)的最小划分数,使得每个点划分集的导出子图是一个森林.众所周知,平面图G的点荫度至多为3.2008年,Raspaud和王维凡证明了:若G是不含κ-圈(κ∈{3,4,5,6})的平面图,则va(G)≤2.本文推广了上述结果,得到了点荫度至多为2的一个局部条件,即若平面图G的每一个点都不同时与3-圈、4-圈、5-圈和6-圈关联,则va(G)≤2.     

Adjacent Vertex Distinguishing Edge Coloring of Planar Graphs with Girth at Least 5北大核心CSCD

An adjacent vertex distinguishing edge-colorings of a graph G is a proper edge coloring of G such that any pair of adjacent vertices have distinct sets of colors. The minimum number of color required for an adjacent vertex distinguishing edge-coloring of G is denoted by χa'(G). In this paper, we prove that if G is a planar graph with girth at least 5 and without isolated edges, then χa'(G)≤ max{8,Δ(G)+1}. © 2022, Chinese Academy of Sciences. All right reserved.