共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1. 相似文献
4.
对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e1,e2满足φ(e1)≠φ(e2),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a’l(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a’l(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果. 相似文献
5.
设图$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.
《数学的实践与认识》2015,(23)
对图G的一个正常边染色,如果图G的任何一个圈至少染三种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G)都有ф(e)∈L(e),则称ф为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.证明若图G是一个平面图,且它的最大度△≥8,围长g(G)≥6,则a′_(list)(G)=△. 相似文献
7.
记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的. 相似文献
8.
9.
《中国科学:数学》2020,(2)
设d_1,d_2,...d_k为尼个非负整数.若图G的顶点集V可划分成k个子集合V_1,V_2…,V_k,使得对于任意的i∈{1,2,...,k},由V_i导出的子图G[V_i]的最大度至多为d_i,则称图G是(d_1,d_2,...,d_k)-可染的.1976年,Steinberg猜想:不含4-圈和5-圈的平面图是(0,0,0)-可染的.在Steinberg猜想的驱动下,人们证明了以下三个结论:(1)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是列表(1,1,1)-可染的;(2)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是(1,1,0)-可染的;(3)对每一个i∈{5,6,7,8},不含4-圈和i-圈的平面图是(2,0,0)-可染的.为使结论(3)更加完整,本文证明不含4-圈和9-圈的平面图是(2,0,0)-可染的. 相似文献
10.
对于一个给定的最大度为5的平面图G,(1)图G是9-列表全可染的;(2)若图G中不含5-圈,则G是8-列表全可染色的;(3)若图G不含5-圈,并且最大度点最多邻接两个3-面,则图G为7-列表全可染色的;(4)若图G中不含C4,C5,C7,C8,则图G是6-列表全可染色的;(5)若图G的最大的平均度mad(G)<20/7,则图G是6-列表全可染色的. 相似文献
11.
12.
图G的injective k-染色是指映射c:V(G)→{1,2,…,k},使有公共邻点的两个顶点u,v满足c(u)≠c(v),用X_i(G)表示使G有一个injective k-染色的最小正整数k.对g(G)≥5的平面图G,若△(G)≥20,证明了X_i(G)≤△+3. 相似文献
13.
14.
15.
假设G是一个平面图.如果e1和e2是G中两条相邻边且在关联的面的边界上连续出现,那么称e1和e2面相邻.图G的一个弱边面κ-染色是指存在映射π:E∪F→{1,…,κ},使得任意两个相邻面、两条面相邻的边以及两个相关联的边和面都染不同的颜色.若图G有一个弱边面κ-染色,则称G是弱边面κ-可染的.平面图G的弱边面色数是指G是弱边面κ-可染的正整数κ的最小值,记为χef(G).2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文证明了外平面图满足此猜想,即:外平面图是弱边面5-可染的. 相似文献
16.
17.
《高校应用数学学报(A辑)》2020,(3)
假设e1和e2是两条相邻边,若它们关联同一个面且在该面的边界上连续出现,则称e1和e2是面相邻的.平面图G是弱点边k-可染的是指存在映射π:V (G)∪E(G)→{1,···, k},使得任意两个相邻的顶点,任意两条面相邻的边,以及任意两个相关联的顶点和边都染不同的颜色.文中利用数学归纳法证明了:哈林图(Halin graph)是弱点边5-可染的,并给出可达到上界5的例子. 相似文献
18.
图G的k-2-距离染色是指一个映射φ:V(G)→{1,2,…,k},满足对任意距离小于等于2的顶点对u,v,有φ(u)≠φ(v).2-距离色数χ_2(G)是指使得图G是k-2-距离染色的最小的k.本文证明:对于g(G)≥5且△(G)≥44的平面图G,有χ_2(G)≤△(G)+4. 相似文献
19.
设G=(V,E,F)是一个无环的连通平面图,其中V表示点集,E表示边集,F表示面集.对于任意的两条相邻边e_1和e2,如果它们关联同一个面且在该面的边界上连续出现,那么称e_1和e2是面相邻的.图G是弱边面k-可染的是指存在一个映射π:EUF→{1,2,…,k},使得任意两个相关联的边和面,任意两个相邻的面,以及任意两条面相邻的边都染不同的颜色.平面图G的弱边面染色数是指G是弱边面k-可染的数k的最小值,用_(ef)(G)表示.2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文我们给出此猜想的一个充分条件,即证明:哈林图是弱边面5-可染的,其中上界5是最好可能的. 相似文献
20.
《数学的实践与认识》2020,(10)
如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K_(1*r,3*(k-2))具有M(k)性质,且当r≥2时,m(K_(1*r,3*(k-2)))=k.本文将上述结论推广到每一个k,证明了对任意r∈N~+,k≥3,图K_(1*r,3*(k-2))具有M(k)性质,且当k≥4,r≥(k-2)时,m(K_(1*r,3*(k-2)))=k.此外,得到图K_(1,3,3,3)的m数为4,该图是图K_(1*r,3*(k-2))中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题. 相似文献