排序方式: 共有42条查询结果,搜索用时 15 毫秒
31.
一个平面图G被称为1-外平面图如果存在一个顶点u 使得G- u 是一个外平面图.本文证明了Melnikov 的边面染色猜想对所有1-外平面图成立. 相似文献
32.
王维凡 《纯粹数学与应用数学》2000,16(2):1-6
一个图G称为是m-ST可分解的,如果G能分解为m个边不交生成树的并,本文研究了一个图是m-ST可分解的若干性质,并证明了两类平面图是2-ST可分解的。 相似文献
33.
图 $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$中含有两个相邻最大度点. 相似文献
34.
消防员问题可视为传染病、火灾、谣言、计算机病毒等传播的一个简化模型.假设一把火在一个图的某个点或多个点燃起,消防员选择若干个未着火的顶点进行防护,然后火蔓延到前一步着火点的未燃邻点.当火不再蔓延时整个过程结束.消防员问题自1995年提出以来引起了人们的广泛关注.本文简述了与消防员问题相关的最近研究进展,包括算法复杂性、无限图和有向图的消防员问题、图的存活率、图的燃烧数及一些有待于进一步研究的问题. 相似文献
35.
图G的线性2-荫度la_2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树是长度至多为2的路.本文证明了若G是最大度为Δ(G)的K_4-minor-free图,则la_2(G)≤(Δ(G) 5)/2. 相似文献
36.
37.
38.
设Hn(n≥5)表示一个图:以1,2,...,n为顶点,两个点i和j是相邻的当且仅当|i-j|≤2,其中加法取模n.这篇文章证明了,Hn的色数等于它的选择数.结果被用于刻画最大度至多2的图的列表全色数. 相似文献
39.
1IntroductionWe only consider simple graphs in this paper unless otherwise stated.For a plane graphG,we denote its vertex set,edge set,face set,minimum degree,and maximum degree by V(G),E(G),F(G),δ(G),and?(G),respectively.For v∈V(G),let dG(v)denote the … 相似文献
40.