可平面图的r-hued染色(英文)

令k0,r0是两个整数.图G的一个r-hued染色是一个正常k-染色?使得每个度为d(v)的顶点v相邻至少min{d(v),r}个不同的颜色.图G的r-hued色数是使得G存在r-hued染色的最小整数k,记为χ_r(G).文章证明了,若G为不含i-圈,4≤i≤9,的可平面图,则χ_r(G)≤r+5.这一结果意味着对于无4-9圈的可平面图,r-hued染色猜想成立.     

平面图和系列平行图的无圈边染色

图$G$的正常边染色称为无圈的, 如果图$G$中不含2-色圈, 图$G$的无圈边色数用$a''(G)$表示, 是使图$G$存在正常无圈边染色所需要的最少颜色数. Alon等人猜想: 对简单图$G$, 有$a''(G)\leq{\Delta(G)+2}$. 设图$G$是围长为$g(G)$的平面图, 本文证明了: 如果$g(G)\geq3$, 则$a''(G)\leq\max\{2\Delta(G)-2,\Delta(G)+22\}$; 如果 $g(G)\geq5$, 则$a''(G)\leq{\Delta(G)+2}$; 如果$g(G)\geq7$, 则$a''(G)\leq{\Delta(G)+1}$; 如果$g(G)\geq16$并且$\Delta(G)\geq3$, 则$a''(G)=\Delta(G)$; 对系列平行图$G$, 有$a''(G)\leq{\Delta(G)+1}$.     

一个关于平面图的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$.     

没有K4-图子式的图的邻点可区别全染色

图 $G$ 的邻点可区别全染色是$G$ 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. $G$的邻点可区别全色数$\chi''''_{a}(G)$是使得$G$有一个$k$-\!邻点可区别全染色的最小的整数$k$. 本文完整刻画了没有$K_4$-\!图子式的图的邻点可区别全色数. 证明了：如果 $G$是一个满足最大度$\Delta \ge 3$且没有$K_4$-\!图子式的图, 则$\Delta+1\le \chi''''_{a}(G)\le \Delta+2$, 且$\chi''''_{a}(G)=\Delta+2$当且仅当$G$中含有两个相邻最大度点.     

关于图中存在不含给定k-因子的[a,b]-因子的度条件

设$1\leq a<b, 0\leq k$是整数. 设$G$是一个含有$k$-因子$Q$且阶为$|G|$的图. 设\delta(G)$表示$G$的最小度, 且$\delta(G)\geq a+k$. 如果$Q$连通, 设$\varepsilon=k$, 否则设$\varepsilon=k+1$.证明:当$b\geq a+\varepsilon-1$时, 如果对$G$的任意两个不相邻的点$x$和$y$都有max$\{d_G(x),d_G(y)\}\geq {\rm max}\{{{a|G|} \over {a+b}},{{(|G|+(a-1)(2a+b+\varepsilon-2))} \over {b+1}}\}+k$, 那么$G$有一个$[a, b]$-因子$F$ 使得 $E(F)\cap E(Q)=\emptyset$. 这个度条件是最佳的, 条件$b\geqa+\varepsilon-1$不能去掉. 进一步,得到图存在含给定$k$-因子的$[a, b]$-因子的度条件.     

高度正则图的全着色

一个图$G$的全色数$\chi_T(G)$ 是对$G$的边和顶点着色的最小数, 使得相关联或相邻元素着不同色. 证明了如果$G$是正则图并且$d(G)\ge\cfrac{2}{3}|V(G)|+\cfrac{23}{6},$ 这里$d(G)$ 表示在$G$中顶点的度, 则$\chi_T(G)\leq d(G)+2$.     

偶图Kn,r-A(|A|≤3)的圈长分布唯一性

阶为$n$的图$G$的圈长分布是序列$(c_1,c_2,\cdots,c_n)$, 其中$c_i$ 是图$G$ 中长为$i$的圈数.设$A\subseteq E(K_{n,r})$.本文得到如下结果: 若$\mid A\mid =2$,且$n\leq r\leq \min\{n+6,2n-5\}$,则$G=K_{n,r}-A$是由它的圈长分布确定的;若$\mid A\mid =3$,且$n \leq r\leq \min\{n+6,2n-7\}$,则$G=K_{n,r}-A$也是由它的圈长分布确定的.     

$P_m\times K_n$的邻点可区别全色数

设 $G$ 是简单图. 设$f$是一个从$V(G)\cup E(G)$ 到$\{1, 2,\cdots, k\}$的映射. 对每个$v\in V(G)$, 令 $C_f (v)=\{f(v)\}\cup \{f(vw)|w\in V(G), vw\in E(G)\}$. 如果 $f$是$k$-正常全染色, 且对任意$u, v\in V(G), uv\in E(G)$, 有$C_f(u)\ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $\chi_{at}(G)=\min\{k|G$ 有$k$-AVDTC\}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数.     

非负特征图的线性染色

如果图$G$的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图$G$ 的线性染色.图$G$的线性色数用lc$(G)$表示,是指$G$的所有线性染色中所用的最少颜色的个数. \qquad 证明了: 对于每一个最大度为$\Delta(G)$围长为$g(G)$的非负特征图$G$,若存在一个有序对$(\Delta,g)\in\{(13,7),(9,8),(7,9),(5,10), (3,13)\}$, 使得$G$满足$\Delta(G)\ge\Delta$且$g(G)\ge g$,则lc$(G)=\lceil \frac {\Delta(G)}2\rceil+1$.     

最大度大于等于7的平面图的线性荫度

图的染色问题在组合优化、计算机科学和Hessians矩阵的网络计算等方面具有非常重要的应用。其中图的染色中有一种重要的染色——线性荫度,它是一种非正常的边染色,即在简单无向图中,它的边可以分割成线性森林的最小数量。研究最大度$\bigtriangleup（G）\geq7$的平面图$G$的线性荫度,证明了对于两个固定的整数$i$,$j\in\{5,6,7\}$,如果图$G$中不存在相邻的含弦$i$,$j$-圈,则图$G$的线性荫度为$\lceil\frac\bigtriangleup2\rceil$。     

边临界图的新下界

图$G$ 为简单的第二类连通图, 且对$G$ 的任意边$e$,有$\chi^{\prime}(G-e)<\chi^{\prime}(G)$, 则称 $G$是临界的.该文给出了阶为$n$ 边数为$m$的$\Delta$ -临界图的新下界, 即$m\geq(3\Delta+6)n/10$, 这里$1\leq\Delta\leq18$     

图的上可嵌入性与围长及相邻顶点度和

$G$是一个阶为$n$围长为$g$的简单图, $u$和$v$是$G$中任意两个相邻顶点, 如果$d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 5$, 则$G$是上可嵌入的; 如果$G$是2-\!边连通(或3-\!边连通)图, 则当 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 3$ (或 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g - 5$)时$G$是上可嵌入的, 并且上面3个下界都是紧的.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

毛毛虫树的最优$L(2,1,1)$-标号

图$G$的一个$L(2,1,1)$-标号是指从顶点集$V(G)$到非负整数集上的一个函数$f$,满足: 当$d(u,v)=1$时, $|f(u)-f(v)|\ge 2$, 当$d(u,v)=2$时, $|f(u)-f(v)|\ge 1$, 当$d(u,v)=3$时, $|f(u)-f(v)|\ge 1$. 若一个$L(2,1,1)$-标号中的所有像元素都不超过整数$k$, 则称之为图$G$的$k$-$L(2,1,1)$-标号. 图$G$的$L(2,1,1)$-标号数, 记作$\lambda 2,1,1(G)$,是使得图$G$存在$L(2,1,1)$-标号的最小整数$k$. 本文研究了毛毛虫树的最优$L(2,1,1)$-标号,给出了一些$L(2,1,1)$-标号数达到上界的充分条件,并完全刻画了最大边度为6的毛毛虫树的$L(2,1,1)$-标号数.     

图加一条边后的带宽和

令$BS(G,f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|$, 其中$f$为$V(G)\rightarrow\{1,2,\cdots,|V(G)|\}$的双射, 并称$BS(G)=\min\limits_{f}BS(G,f)$为图$G$的带宽和. 讨论顶点数为$n$的简单图$G$加上一条边$e\in\overline{E(G)}$后, 带宽和$BS(G+e)$与$BS(G)$的关系, 得其关系式$BS(G)+1\leq BS(G+e)\leq BS(G)+n-1$. 并证明此不等式中等号可取到, 即存在图$G_{1}$和$G_{2}$使得$BS(G_{1}+e)=BS(G_{1})+1$, $BS(G_{2}+e)=BS(G_{2})+n-1$.     

嵌入曲面的特殊图的边染色

设图\,$G$\,是嵌入到欧拉示性数\,$\chi(\Sigma)\geq 0$\,的曲面\,$\Sigma$\,上的图, $\chi'(G)$\,和\,$\Delta(G)$\,分别表示图\,$G$\,的边色数和最大度. 如果\,$\Delta(G)\geq 4$\,且\,$G$\,满足以下条件: (1)\,图$G$中的任意两个三角形$T_1$, $T_2$的距离至少是$2$; (2)\,图\,$G$\,中\,$i$-圈和\,$j$-圈的距离至少是\,$1$, $i,j\in\{3,4\}$; (3)\,图\,$G$\,中没有\,$5$-圈, 则有\,$\Delta(G)=\chi'(G)$.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

$k$-广义拟树的第一个leap Zagreb 指标

图$G$的第一个leap Zagreb指标定义如下: $LM_1(G)=\sum_(v\in v(G)}d_2(v/G)^2$, 其中$d_2(v/G)$是离点$v$的距离为2的顶点. 令$\mathcal{QT}^{(k)}(n)$是有$n$个顶点的$k$-广义拟树的集合.若$G\in \mathcal{QT}^{(k)}(n)$, 本文给出了图$G$的第一个leap Zagreb指标的范围.     

关于乘积Sombor指数的极值(分子)树

拓扑指数是一类可以用来预测化合物的物理化学性质的数值不变量, 其并被广泛用于量子化学、分子生物学和其他研究领域. 对于一个顶点集为$V(G)$、边集为$E(G)$的(分子)图$G$, 其Sombor指数定义为$SO(G)=\sum\limits_{uv\in E(G)}\sqrt{d_{G}^{2}(u)+d_{G}^{2}(v)}$, 其中$d_{G}(u)$表示顶点$u$在$G$中的度. 相应地, 乘积Sombor指数定义为$\prod\nolimits_{SO}(G)= \prod\limits_{uv\in E(G)}\sqrt{d_{G}^{2}(u)+d_{G}^{2}(v)}$. 分子树是最大度$\Delta\leq 4$的树. 在本文中, 我们首先确定了乘积Sombor指数最大的分子树, 然后我们确定了乘积Sombor指数的前十三小的(分子)树.     

图$P_m\times P_n, P_m\times C_n$ 和C_m\times C_n$}的邻点可区别全色数的注记

设 $G$ 是一个简单图. 设$f$是从$V(G) \cup E(G)$到 $\{1, 2,\ldots, k\}$的一个映射.对任意的 $v\in V(G)$, 设$C_f(v)=\{f(v)\}\cup \{f (vw)|w\in V(G),vw\in E(G)\}$ . 如果 $f$ 是一个 $k$-正常全染色, 且对 $u, v\in V(G),uv\in E(G)$, 有 $C_f(u)\neq C_f(v)$, 那么称 $f$ 为$k$-邻点可区别全染色 (简记为$k$-$AVDTC$). 设