共查询到19条相似文献,搜索用时 46 毫秒
1.
图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1. 相似文献
2.
3.
图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)-标号数,本文给出了一个完全的刻画. 相似文献
4.
5.
《数学的实践与认识》2016,(10)
图G的Ⅰ-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻顶点的颜色不同,任意两条相邻边的颜色不同.在图G的一个Ⅰ-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个Ⅰ-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别Ⅰ-全染色所用的最少颜色的数目称为图G的邻点可区别Ⅰ-全色数.应用构造具体染色的方法给出了路与星、扇、轮图的积图的邻点可区别Ⅰ-全色数 相似文献
6.
图G的一个L(2.1)-标号是从顶点集V(G)到非负整数的一个函数f,使得若d(u,v)=1时,有|f(u)-f(v)|≥2;若d(u,v)=2时,有|f(u)-f(v)|≥1.图G的L(2.1)-标号数λ(G)是G的所有L(2.1)-标号下的跨度max{f(v):v∈V(G)}的最小数.图Fn+1*为扇图的路上每个顶点增加一个悬挂边得到的图.图Hn为轮图的圈上每个顶点增加一个悬挂边得到的图.本文确定了图Fn+1*与Hn的L(2.1)-标号数. 相似文献
7.
图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v)v∈V(G)}=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立. 相似文献
8.
设λ1,λ2,…,λn是n阶图G的特征值,图G的能量是E(G)=|λ1| |λ2| … |λn|,设G(n)是n个顶点n 1条边的恰有两个圈的连通二部图的集合,Z(n;4,4)是G(n)中的一个图,它的两个长为4的圈恰有一个公共点,其余n-7个点都是悬挂点且均与这个公共点相邻.文中证明了Z(n;4,4)是G(n)中具有最小能量的图。 相似文献
9.
10.
设图$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$. 相似文献
11.
Planar graphs without 5-cycles or without 6-cycles 总被引:1,自引:0,他引:1
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. 相似文献
12.
A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge. A proper vertex k-coloring of a graph G is defined as a vertex coloring from a set of k colors such that no two adjacent vertices have the same color. A graph that can be assigned a proper k-coloring is k-colorable. A cycle is a path of edges and vertices wherein a vertex is reachable from itself. A cycle contains k vertices and k edges is a k-cycle. In this paper, it is proved t... 相似文献
13.
Lin SUN 《数学学报(英文版)》2021,(6):992-1004
A proper vertex coloring of a graph is acyclic if every cycle uses at least three colors. A graph G is acyclically k-choosable if for any list assignment L = {L(v) : v ∈ V(G)} with |L(v)| ≥ k for all v ∈ V(G), there exists a proper acyclic vertex coloring φ of G such that φ(v) ∈ L(v) for all v ∈ V(G). In this paper, we prove that if G is a planar graph and contains no 5-cycles and no adjacent 4-cycles, then G is acyclically 6-choosable. 相似文献
14.
A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define for and We say that is -colorable if has a 2-coloring such that is an empty set or the induced subgraph has the maximum degree at most for and Let be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether is -colorable is NP-complete for every positive integer Moreover, we construct non--colorable planar graphs without 4-cycles and 5-cycles for every positive integer In contrast, we prove that is -colorable where and 相似文献
15.
16.
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(G). 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 it is proved that every planar graph with neither 4-cycles nor chordal 6-cycles is acyclically 5-choosable. This generalizes the results of [M. Montassier, A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory 54 (2007) 245-260], and a corollary of [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (4) (2006) 281-300]. 相似文献
18.
Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al. 2002) [7]. This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs.Some sufficient conditions are also obtained for a planar graph to be acyclically 4-choosable and 3-choosable. In particular, acyclic 4-choosability was proved for the following planar graphs: without 3-cycles and 4-cycles (Montassier, 2006 [23]), without 4-cycles, 5-cycles and 6-cycles (Montassier et al. 2006 [24]), and either without 4-cycles, 6-cycles and 7-cycles, or without 4-cycles, 6-cycles and 8-cycles (Chen et al. 2009 [14]).In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles adjacent to a triangle is acyclically 4-choosable, which covers these four results. 相似文献
19.
Edge choosability and total choosability of planar graphs with no 3-cycles adjacent 4-cycles 总被引:1,自引:0,他引:1
Two cycles are said to be adjacent if they share a common edge. Let G be a planar graph without triangles adjacent 4-cycles. We prove that if Δ(G)≥6, and and if Δ(G)≥8, where and denote the list edge chromatic number and list total chromatic number of G, respectively. 相似文献