ON THE TOTAL COLORING OF GRAPH G ∨H

数学物理学报(英文版) ›› 1996, Vol. 16 ›› Issue (2): 162-169.

ON THE TOTAL COLORING OF GRAPH G ∨H

许宝刚

Math. of Dept., Shandong University, Jinan 250100, China

收稿日期:1994-03-21 修回日期:1995-02-23 出版日期:1996-06-25 发布日期:1996-06-25

ON THE TOTAL COLORING OF GRAPH G ∨H

Xu Baogang

Math. of Dept., Shandong University, Jinan 250100, China

Received:1994-03-21 Revised:1995-02-23 Online:1996-06-25 Published:1996-06-25

摘要/Abstract

摘要： The total chromatic number X_T(G) of graph G is the least number of colors assigned to VE(G) such that no adjacent or incident elements receive the same color.Given graphs G₁,G₂, the join of G₁ and G₂, denoted by G₁∨G₂, is a graph G, V(G)=V(G₁)∪V(G₂) and E(G)=E(G₁)∪E(G₂) ∪{uv|u∈V(G₁), v ∈V(G₂)}. In this paper, it's proved that if v(G)=v(H), both G^c and H^c contain perfect matching and one of the followings holds:(i)Δ(G)=Δ(H) and there exist edge e∈ E(G), e'∈E(H) such that both G-e and H-e' are of Class l; (ii)Δ(G)<Δ(H) and there exixst an edge e ∈E(H) such that H-e is of Class 1, then, the total coloring conjecture is true for graph G ∨H.

关键词: graph, join of graphs, total chromatic number

Abstract: The total chromatic number X_T(G) of graph G is the least number of colors assigned to VE(G) such that no adjacent or incident elements receive the same color.Given graphs G₁,G₂, the join of G₁ and G₂, denoted by G₁∨G₂, is a graph G, V(G)=V(G₁)∪V(G₂) and E(G)=E(G₁)∪E(G₂) ∪{uv|u∈V(G₁), v ∈V(G₂)}. In this paper, it's proved that if v(G)=v(H), both G^c and H^c contain perfect matching and one of the followings holds:(i)Δ(G)=Δ(H) and there exist edge e∈ E(G), e'∈E(H) such that both G-e and H-e' are of Class l; (ii)Δ(G)<Δ(H) and there exixst an edge e ∈E(H) such that H-e is of Class 1, then, the total coloring conjecture is true for graph G ∨H.

Key words: graph, join of graphs, total chromatic number

许宝刚. ON THE TOTAL COLORING OF GRAPH G ∨H[J]. 数学物理学报(英文版), 1996, 16(2): 162-169.

Xu Baogang. ON THE TOTAL COLORING OF GRAPH G ∨H[J]. Acta mathematica scientia,Series B, 1996, 16(2): 162-169.

[1]	林勇, 吴艺婷. BLOW-UP PROBLEMS FOR NONLINEAR PARABOLIC EQUATIONS ON LOCALLY FINITE GRAPHS[J]. 数学物理学报(英文版), 2018, 38(3): 843-856.
[2]	周少波, 薛明皋. EXPONENTIAL STABILITY FOR NONLINEAR HYBRID STOCHASTIC PANTOGRAPH EQUATIONS AND NUMERICAL APPROXIMATION[J]. 数学物理学报(英文版), 2014, 34(4): 1254-1270.
[3]	K. BALACHANDRAN, S. KIRUTHIKA, J. J. TRUJILLO. EXISTENCE OF SOLUTIONS OF NONLINEAR FRACTIONAL PANTOGRAPH EQUATIONS[J]. 数学物理学报(英文版), 2013, 33(3): 712-720.
[4]	Muhammad IMRAN, Syed Ahtsham ul Haq BOKHARY, Ali AHMAD, Andrea SEMANICOVá-FE?OVCíKOVá. ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION[J]. 数学物理学报(英文版), 2013, 33(1): 187-206.
[5]	程志云, 高红铸. SOME APPLICATIONS OF PLANAR GRAPH IN KNOT THEORY[J]. 数学物理学报(英文版), 2012, 32(2): 663-671.
[6]	Sarp Adali. VARIATIONAL PRINCIPLES FOR NONLOCAL CONTINUUM MODEL OF ORTHOTROPIC GRAPHENE SHEETS EMBEDDED IN AN ELASTIC MEDIUM[J]. 数学物理学报(英文版), 2012, 32(1): 325-338.
[7]	陈恕行. A NONLINEAR LAVRENTIEV-BITSADZE MIXED TYPE EQUATION[J]. 数学物理学报(英文版), 2011, 31(6): 2378-2388.
[8]	A. Cheer, Harry A. Dwyer, T. Kim. NEW METHOD FOR IMPROVED CALCULATIONS OF UNSTEADY COMPLEX FLOWS IN LARGE ARTERIES[J]. 数学物理学报(英文版), 2011, 31(6): 2247-2264.
[9]	陈爱莲, 张福基, 李皓. THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS[J]. 数学物理学报(英文版), 2011, 31(3): 1155-1166.
[10]	M.I.Ostrovskii . MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS[J]. 数学物理学报(英文版), 2011, 31(2): 634-640.
[11]	张良才, 施武杰. OD-CHARACTERIZATION OF ALMOST SIMPLE GROUPS RELATED TO U₆(2)[J]. 数学物理学报(英文版), 2011, 31(2): 441-450.
[12]	东瑜昕, 嵇庆春, 张玮. FINITENESS OF HIGHER CODIMENSIONAL DISJOINT MINIMAL GRAPHS[J]. 数学物理学报(英文版), 2010, 30(1): 107-112.
[13]	原晋江. INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS[J]. 数学物理学报(英文版), 2006, 26(4): 577-584.
[14]	张忠辅; 王维凡; 李敬文; 姚兵; 卜月华. EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE[J]. 数学物理学报(英文版), 2006, 26(3): 477-482.
[15]	杨超; 张建中. ON THE BOTTLENECK CAPACITY EXPANSION PROBLEMS ON NETWORKS[J]. 数学物理学报(英文版), 2006, 26(2): 202-208.

ON THE TOTAL COLORING OF GRAPH G ∨H

ON THE TOTAL COLORING OF GRAPH G ∨H

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10