边染色图中的彩色围长

研究了在边染色图中有关颜色度与彩色围长的关系,得出了一个结论:若G是具有n个顶点(n≥3)的边染色图,对任意v∈V(G),如果dc(v)≥n/(2-α),其中α=3/(s-3)ln(2+7^(1/2))/3 ,s>3且s∈N,则有gH(G)≤s。

边染色图中的长彩色路问题

研究了边染色图中的彩色路,给出了满足一定色度条件下的边染色中彩色路的长度的下界。

边染色图中的正常染色的路和圈

讨论了无三角形的边染色图中的正常染色的路和圈,在无三角形图中改进了原有的结果。证明了在顶点的最小色度至少为d(d≥2)的条件下,边染色图G或者存在长至少为4d-2的正常染色的路,或者存在长至少为2「2d/3的正常染色的圈。

边染色图中的2-因子

令G是含n个点的边染色图,对G中任意顶点x,定义其色邻域CN(x)为集合{c(xy)|xy∈E(G),y∈V(G)}。如果G中任意相邻的两条边都染有不同的颜色,就称G是正常染色的。证明了如果边染色图G满足对V(G)中任意两点u,v有|CN(u)∪CN(v)|≥4n/3+8,则图G含有一个正常染色2-因子。

图P_2×C_n 的均匀邻强边色数(英文)

对图 G(V,E) ,一正常边染色 f 若满足 :(1)对 uv∈ E(G) ,f[u]≠ f[v],其中 f[u]={ f(uv) | uv∈E} ;(2 )对任意 i≠ j,有‖ Ei| - | Ej‖≤ 1,其中 Ei={ e| e∈ E(G)且 f(e) =i} .则称 f 为 G(V,E)的一 k-均匀邻强边染色 ,简称 k- EASC,并且称χ′eas(G) =min{ k|存在 G(V,E)的一 k- EASC为 G(V,E)的均匀邻强边色数。本文得到了图 P2 × Cn 的均匀邻强边色数。

图P_m+P_n的Smarandachely邻点边色数

对简单图G(V,E),f是从E(G)到{1,2,…,k}(k是自然数)的映射,若f满足:(1)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(2)uv∈E(G),|C(u)\C(v)|≥1,并且|C(v)\C(u)|≥1;则称f是G的Smarandachely邻点边染色。文章给出了m(m=2,3,4)阶路与n阶路的联图的Smarandachely邻点边色数。其中C(u)={f(uv)|uv∈E(G)且u≠v}。

关于图的点可区别边染色猜想的一点注

图G的一个k-正常边染色f被称为点可区别的是指任意两点的点及其关联边所染色集合不同,所用最少颜色数被称为G的点可区别边色数,张忠辅教授提出一个猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,图G一定有一个子图H,使得G的点可区别的边色数不超过子图的.本文证明了对于最大度△≤6时,猜想正确.

关于图的点可区别边染色的一个猜想

图G的一个k-正常边染色f被称为点可区别的是指任意两个不同点的点及其关联边所染色集合不同,所用最少染色数被称为G的点可区别边色数,张忠辅教授提出一猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,,满足图G一定有一个子图H,且母图的点可区别的边色数小于子图的.本文证明了对于最大度小于9时,此猜想正确.

The Incidence Coloring Number of Complete k-Partite Graph

The concept of the incidence chromatic number of a graph was introduced by Brualdi and Massey. They conjectured that every graph G can be incidence colored with Δ (G) +2 colors. In this paper, the trueness of this conjecture for complete k partite graph was proved, and the incidence chromatic number of complete k partite graphs was calculated.

图的Smarandachely邻点无圈边色数的一个上界

提出了图的Smarandachely邻点无圈边染色的概念,讨论了图的Smarandachely邻点无圈边染色与邻点可区别无圈边染色之间的关系,并运用概率方法得到了图G的Smarandachely邻点无圈边色数的一个上界,其中G为无孤立边的图.

关于图K_(2n)-E(C_4)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数.

On the Adjacent Strong Edge Coloring of Halin Graphs

A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC: and x'as(G) = min{k|k-ASEC of G} is called the adjacent strong edge chromatic number. In this paper, we study the x'as(G) of Halin graphs with △A(G)≥5.

On the Adjacent Strong Edge Coloring of Outer Plane Graphs

A k-adjacent strong edge coloring of graph G(V, E) is defined as a proper k-edge coloring f of graph G(V, E) such that f[u] ≠ f[v] for every uv ∈ E(G), where f[u] = {f(uw)|uw ∈ E(G)} and f(uw) denotes the color of uw, and the adjacent strong edge chromatic number is defined as x'as(G) = min{k| there is a k-adjacent strong edge coloring of G}. In this paper, it has been proved that △ ≤ x'as(G) ≤ △ + 1 for outer plane graphs with △(G) ≥ 5, and X'as(G) = △ + 1 if and only if there exist adjacent vertices with maximum degree.

Adjacent Strong Edge Chromatic Number of Series-Parallel Graphs

In this paper, we will study the adjacent strong edge coloring of series-parallel graphs, and prove that series-parallel graphs of △(G) = 3 and 4 satisfy the conjecture of adjacent strong edge coloring using the double inductions and the method of exchanging colors from the aspect of configuration property. For series-parallel graphs of △(G) ≥ 5, △(G) ≤ x'as(G) ≤ △(G) + 1. Moreover, x'as(G) = △(G) + 1 if and only if it has two adjacent vertices of maximum degree, where △(G) and X'as(G) denote the maximum degree and the adjacent strong edge chromatic number of graph G respectively.

关于K_(2n)-E(C_m)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为X'_(vd)(G).用k_(2n)-E(C_m)表示2n阶完全图删去其中一条m阶路的边后得到的图,得到了K_(14)-E(C_4),K_(16)-E(C_4),K_(18)-E(C_5),K_(20)-E(C_5)的点可区别边色数分别为14,16,18,20.

Acyclic edge coloring of planar graphs without adjacent cycles

A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.

Acyclic edge coloring of graphs with large girths

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ'a(G), is the least number of colors such that G has an acyclic edge k-coloring. Let G be a graph with maximum degree Δ and girth g(G), and let 1≤r≤2Δ be an integer. In this paper, it is shown that there exists a constant c > 0 such that if g(G)≥cΔ r log(Δ2/r) then χa(G)≤Δ + r + 1, which generalizes the result of Alon et al. in 2001. When G is restricted to series-parallel graphs, it is proved that χ'a(G) = Δ if Δ≥4 and g(G)≥4; or Δ≥3 and g(G)≥5.

Asymptotic existence of frame-GBTDs

Generalized balanced tournament designs(GBTDs) are an equivalent characterization of a class of equitable symbol weight codes. Motivated by the construction of GBTDs, we establish in this paper an asymptotic existence theorem for frame-GBTDs of type gnand block size k via decompositions of edge-colored complete digraphs into prescribed edge-colored subgraphs.

THE METHOD OF COLORING IN GRAPHS AND ITS APPLICATION

Graph coloring has interesting real life applications in optimization and network design. In this paper some new results on the acyclic-edge coloring, f-edge coloring, g-edge cover coloring, （g, f）-coloring and equitable edge-coloring of graphs are introduced. In particular, some new results related to the above colorings obtained by the authors are given. Some new problems and conjectures are presented.