共查询到20条相似文献,搜索用时 31 毫秒
1.
The Entire Coloring of Series-Parallel Graphs 总被引:2,自引:0,他引:2
Jian-liangWu Yu-liangWu 《应用数学学报(英文版)》2005,21(1):61-66
The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6. 相似文献
2.
Let G be an outerplanar graph with maximum degree △. Let χ(G^2) and A(G) denote the chromatic number of the square and the L(2, 1)-labelling number of G, respectively. In this paper we prove the following results: (1) χ(G^2) = 7 if △= 6; (2) λ(G) ≤ △ +5 if △ ≥ 4, and ),(G)≤ 7 if △ = 3; and (3) there is an outerplanar graph G with △ = 4 such that )λ(G) = 7. These improve some known results on the distance two labelling of outerplanar graphs. 相似文献
3.
On total chromatic number of planar graphs without 4-cycles 总被引:5,自引:0,他引:5
Min-le SHANGGUAN 《中国科学A辑(英文版)》2007,50(1):81-86
Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture. 相似文献
4.
Yi-chao CHEN & Yan-pei LIU College of Mathematics Econometrics Hunan University Changsha China Department of Mathematics Beijing Jiaotong University Beijing China 《中国科学A辑(英文版)》2007,50(2):292-304
The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less thanβ(G)-1/2β(G)-1β(G) and not larger thanβ(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number. 相似文献
5.
The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2. 相似文献
6.
Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160
Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!]. 相似文献
7.
A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, we prove that every graph G with girth g(G) and maximum degree Δ(G) that can be embedded in a surface of nonnegative characteristic has lc(G) = Δ(2G )+ 1 if there is a pair (Δ, g) ∈ {(13, 7), (9, 8), (7, 9), (5, 10), (3, 13)} such that G s... 相似文献
8.
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1.
This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation
of Shandong Province (Grant No. Y2008A20). 相似文献
9.
Jing-wen Li Zhi-wen Wang Jaeun Lee Moo Young Sohn Zhong-fu Zhang En-qiang Zhu 《应用数学学报(英文版)》2010,26(3):525-528
In this paper we get some relations between α(G), α'(G), β(G), β'(G) and αT(G), βT(G). And all bounds in these relations are best possible, where α(G), α'(G),/3(G), β(G), αT(G) and βT(G) are the covering number, edge-covering number, independent number, edge-independent number (or matching number), total covering number and total independent number, respectively. 相似文献
10.
Shi Rong LI 《数学学报(英文版)》2005,21(4):797-802
For a finite group G, let T(G) denote a set of primes such that a prime p belongs to T(G) if and only if p is a divisor of the index of some maximal subgroup of G. It is proved that if G satisfies any one of the following conditions: (1) G has a p-complement for each p∈T(G); (2)│T(G)│= 2: (3) the normalizer of a Sylow p-subgroup of G has prime power index for each odd prime p∈T(G); then G either is solvable or G/Sol(G)≌PSL(2, 7) where Sol(G) is the largest solvable normal subgroup of G. 相似文献
11.
Let G be a 2-edge-connected simple graph with girth g, independence number α(G), and if one of the following two conditions holds
then G is upper embeddable and the lower bound v − 3g + 7 is best possible. Similarly the result for 3-edge-connected simple graph with girth g and independence number α(G) is also obtained.
Huang Yuanqiu: Partially supported by National Science Foundation of China (No. 10771062) and Program for New Century Excellent
Talents in University (No. NCET-07-0276). 相似文献
(1) | α(G) ≤ 2; | |
(2) | α(G) ≥ 3, and for any three nonadjacent vertices v
i
(i = 1,2,3), it has
|
12.
Xiang-en Chen Zhong-fu Zhang 《应用数学学报(英文版)》2008,24(1):55-58
In a paper by Zhang and Chen et al.(see [11]), a conjecture was made concerning the minimum number of colors Xat(G) required in a proper total-coloring of G so that any two adjacent vertices have different color sets, where the color set of a vertex v is the set composed of the color of v and the colors incident to v. We find the exact values of Xat(G) and thus verify the conjecture when G is a Generalized Halin graph with maximum degree at least 6, A generalized Halin graph is a 2-connected plane graph G such that removing all the edges of the boundary of the exterior face of G (the degrees of the vertices in the boundary of exterior face of G are all three) gives a tree. 相似文献
13.
A lower bound on the total signed domination numbers of graphs 总被引:4,自引:0,他引:4
Xin-zhong LU Department of Mathematics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2007,50(8):1157-1162
Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n. 相似文献
14.
The geodetic numbers of graphs and digraphs 总被引:1,自引:0,他引:1
Chang-hong LU~ 《中国科学A辑(英文版)》2007,50(8):1163-1172
For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang. 相似文献
15.
Ying Ying TAN Yi Zheng FAN 《数学学报(英文版)》2008,24(1):139-146
Let G be a mixed glaph which is obtained from an undirected graph by orienting some of its edges. The eigenvalues and eigenvectors of G are, respectively, defined to be those of the Laplacian matrix L(G) of G. As L(G) is positive semidefinite, the singularity of L(G) is determined by its least eigenvalue λ1 (G). This paper introduces a new parameter edge singularity εs(G) that reflects the singularity of L(G), which is the minimum number of edges of G whose deletion yields that all the components of the resulting graph are singular. We give some inequalities between εs(G) and λ1 (G) (and other parameters) of G. In the case of εs(G) = 1, we obtain a property on the structure of the eigenvectors of G corresponding to λ1 (G), which is similar to the property of Fiedler vectors of a simple graph given by Fiedler. 相似文献
16.
The minimum number of total independent partition sets of V ∪ E of graph G(V,E) is called the total chromatic number of G denoted by χ
t
(G). If the difference of the numbers of any two total independent partition sets of V ∪ E is no more than one, then the minimum number of total independent partition sets of V ∪ E is called the equitable total chromatic number of G, denoted by χ
et
(G). In this paper, we obtain the equitable total chromatic number of the join graph of fan and wheel with the same order.
Supported by the National Natural Science Foundation of China (No. 10771091). 相似文献
17.
A connected graph G is said to be factor-critical if G − ν has a perfect matching for every vertex ν of G. In this paper, the factor-critical graphs G with |V(G)| maximum matchings and with |V(G)| + 1 ones are characterized, respectively. From this, some special bicritical graphs are characterized.
This work is supported by the Ph.D. Programs Foundation of Ministry of Education of China (No.20070574006) and the NNSF(10201019)
of China. 相似文献
18.
The semidefinite programming formulation of the Lovász theta number does not only give one of the best polynomial simultaneous
bounds on the chromatic number χ(G) or the clique number ω(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming
formulation can be tightened toward either χ(G) or ω(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed
with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism
groups.
Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged. 相似文献
19.
An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph 总被引:3,自引:0,他引:3
A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to υ, where uυ ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ′
aa
(G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G(V, E) is a graph with no isolated edges, then χ′
aa
(G) ≤ 32Δ.
Supported by the Natural Science Foundation of Gansu Province (3ZS051-A25-025) 相似文献
20.
Jie-hua MAI~ Tai-xiang SUN~ 《中国科学A辑(英文版)》2007,50(12):1818-1824
Let G be a graph and f:G→G be continuous.Denote by R(f) andΩ(f) the set of recurrent points and the set of non-wandering points of f respectively.LetΩ_0(f) = G andΩ_n(f)=Ω(f|_(Ω_(n-1)(f))) for all n∈N.The minimal m∈NU {∞} such thatΩ_m(f)=Ω_(m 1)(f) is called the depth of f.In this paper,we show thatΩ_2 (f)=(?) and the depth of f is at most 2.Furthermore,we obtain some properties of non-wandering points of f. 相似文献