The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, t...The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.展开更多
Melnikov(1975) conjectured that the edges and faces of a plane graph G can be colored with △(G) + 3 colors so that any two adjacent or incident elements receive distinct colors, where △(G) denotes the maximum degree...Melnikov(1975) conjectured that the edges and faces of a plane graph G can be colored with △(G) + 3 colors so that any two adjacent or incident elements receive distinct colors, where △(G) denotes the maximum degree of G. This paper proves the conjecture for the case △(G) ≤4.展开更多
Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ r...Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ receive the color υ.If there exists an(L,d)^(*)-coloring for every list assignment L with|L(υ)|≥k for all υ∈ V(G),then G is called to be(k,d)^(*)-choosable.In this paper,we prove every planar graph G without adjacent k-cycles is(3,1)^(*)-choosable,where k ∈{3,4,5}.展开更多
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 ...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.展开更多
This paper deals with the problem of labeling the vertices, edges and faces of a plane graph. A weight of a face is the sum of the label of a face and the labels of the vertices and edges surrounding that face. In a s...This paper deals with the problem of labeling the vertices, edges and faces of a plane graph. A weight of a face is the sum of the label of a face and the labels of the vertices and edges surrounding that face. In a super d-antimagic labeling the vertices receive the smallest labels and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s appearing in the graph. The paper examines the existence of such labelings for plane graphs containing a special Hamilton path.展开更多
This paper deals with the problem of labeling the vertices, edges and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of ...This paper deals with the problem of labeling the vertices, edges and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face, and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s that appears in the graph. The paper examines the existence of such labelings for disjoint union of plane graphs.展开更多
In this paper, we prove that every plane graph without 5-circuits and without triangles of distance less than 3 is 3-colorable. This improves the main result of Borodin and Raspaud [Borodin, O. V., Raspaud, A.： A suf...In this paper, we prove that every plane graph without 5-circuits and without triangles of distance less than 3 is 3-colorable. This improves the main result of Borodin and Raspaud [Borodin, O. V., Raspaud, A.： A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, Ser. B, 88, 17-27 （2003）], and provides a new upper bound to their conjecture.展开更多
In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G....In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G. This gives a positive support to a conjecture of Borodin and Raspaud which claims that each plane graph without 5-circuits and intersecting triangles is 3-colorable.展开更多
It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in i...It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in it is adjacent to a 4-or a 5-cycle.This improves some known results in this direction.展开更多
Motivated by the connection with the genus of the corresponding link and its application on DNA polyhedral links,in this paper,we introduce a parameter s_(max)(G),which is the maximum number of circles of states of th...Motivated by the connection with the genus of the corresponding link and its application on DNA polyhedral links,in this paper,we introduce a parameter s_(max)(G),which is the maximum number of circles of states of the link diagram D(G)corresponding to a plane(positive)graph G.We show that s_(max)(G)does not depend on the embedding of G and if G is a 4-edge-connected plane graph then s_(max)(G)is equal to the number of faces of G,which cover the results of S.Y.Liu and H.P.Zhang as special cases.展开更多
In 2003, Borodin and Raspaud proved that if G is a plane graph without 5-circuits and without triangles of distance less than four, then G is 3-colorable. In this paper, we prove that if G is a plane graph without 5- ...In 2003, Borodin and Raspaud proved that if G is a plane graph without 5-circuits and without triangles of distance less than four, then G is 3-colorable. In this paper, we prove that if G is a plane graph without 5- and 6-circuits and without triangles of distance less than 2, then G is 3-colorable.展开更多
A graph G is (a, b)-choosable for nonnegative integers a > b if for any given family {A(v)\v ε V(G)} of sets A(v) of cardinality a there exists a family {B(v)\v ε V(G)} of subsets B(v) A(v) of cardinality b such ...A graph G is (a, b)-choosable for nonnegative integers a > b if for any given family {A(v)\v ε V(G)} of sets A(v) of cardinality a there exists a family {B(v)\v ε V(G)} of subsets B(v) A(v) of cardinality b such that B(u) B(v) =θ whenever uv E(G). It is Proved in this paper that every plane graph in which no two triangles share a common vertex is (4m, m)-choosable for every nonnegative integer m.展开更多
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 num...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 give some upper bounds on linear chromatic number for plane graphs with respect to their girth, that improve some results of Raspaud and Wang (2009).展开更多
Cycle reversal had been shown as a powerful method to deal with the relation among orientations of a graph since it preserves the out-degree of each vertex and the connectivity of the orientations. A facial cycle reve...Cycle reversal had been shown as a powerful method to deal with the relation among orientations of a graph since it preserves the out-degree of each vertex and the connectivity of the orientations. A facial cycle reversal on an orientation of a plane graph is an operation that reverses all the directions of the edges of a directed facial cycle. An orientation of a graph is called an α-orientation if each vertex admits a prescribed out-degree. In this paper, we give an explicit formula for the minimum number of the facial cycle reversals needed to transform one α-orientation into another for plane graphs.展开更多
网络遥测是一种新型的网络测量技术,具有实时性强、准确性高、开销低的特点。现有网络遥测技术存在无法收集多粒度网络数据、无法有效存储大量原始网络数据、无法快速提取及生成网络遥测信息、无法利用内核态及用户态特性设计网络遥测...网络遥测是一种新型的网络测量技术,具有实时性强、准确性高、开销低的特点。现有网络遥测技术存在无法收集多粒度网络数据、无法有效存储大量原始网络数据、无法快速提取及生成网络遥测信息、无法利用内核态及用户态特性设计网络遥测方案等问题。为此,提出了一种融合内核态及用户态的、基于遥测数据图和同步控制块的多粒度、可扩展、覆盖全网的网络遥测机制(a nEtwork telemetry mechAnism based on telemetry data Graph in kerneL and usEr mode,EAGLE)。EAGLE设计了一种能够收集多粒度数据且数据平面上灵活可控的网络遥测数据包结构,用于获取上层应用所需的数据。此外,为快速存储、查询、统计、聚合网络状态数据,实现网络遥测数据包所需遥测数据的快速提取与生成,EAGLE提出了一种基于遥测数据图及同步控制块的网络遥测信息生成方法。在此基础上,为了最大化网络遥测机制中网络遥测数据包的处理效率,EAGLE提出了融合内核态及用户态特性的网络遥测信息嵌入架构。在Open vSwitch上实现了EAGLE方案并进行了测试,测试结果表明,EAGLE能够收集多粒度数据并快速提取与生成遥测数据,且仅增加极少量的处理时延及资源占用率。展开更多
The choice number of a graph G,denoted byχl(G) ,is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own l...The choice number of a graph G,denoted byχl(G) ,is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own listno matter whatthe lists are.In this paper,itis showed thatχl(G)≤ 3 for each plane graph of girth not less than 4 which contains no 6- ,7- and 9- cycles展开更多
Using the linear space over the binary field that related to a graph G, a sufficient and necessary condition for the chromatic number of G is obtained.
A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic ...A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic chromatic index of G,denoted by Xa(G),is the smallest integer k such that G is acyclically edge k-colorable.In this paper,we show that if G is a plane graph without 4-,6-cycles and intersecting 3-cycles,△(G)≥9,then Xa(G)≤△(G)+1.展开更多
基金This research is supported by NNSF of China(40301037, 10471131)
文摘The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.
文摘Melnikov(1975) conjectured that the edges and faces of a plane graph G can be colored with △(G) + 3 colors so that any two adjacent or incident elements receive distinct colors, where △(G) denotes the maximum degree of G. This paper proves the conjecture for the case △(G) ≤4.
文摘Given a list assignment of L to graph G,assign a list L(υ)of colors to each υ∈V(G).An(L,d)^(*)-coloring is a mapping π that assigns a color π(υ)∈L(υ)to each vertex υ∈V(G)such that at most d neighbors of υ receive the color υ.If there exists an(L,d)^(*)-coloring for every list assignment L with|L(υ)|≥k for all υ∈ V(G),then G is called to be(k,d)^(*)-choosable.In this paper,we prove every planar graph G without adjacent k-cycles is(3,1)^(*)-choosable,where k ∈{3,4,5}.
基金National Natural Science Foundation of China (No. 19871036) Qinglan talent Funds of Lanzhou Jiaotong University.
文摘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.
文摘This paper deals with the problem of labeling the vertices, edges and faces of a plane graph. A weight of a face is the sum of the label of a face and the labels of the vertices and edges surrounding that face. In a super d-antimagic labeling the vertices receive the smallest labels and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s appearing in the graph. The paper examines the existence of such labelings for plane graphs containing a special Hamilton path.
文摘This paper deals with the problem of labeling the vertices, edges and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face, and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s that appears in the graph. The paper examines the existence of such labelings for disjoint union of plane graphs.
文摘In this paper, we prove that every plane graph without 5-circuits and without triangles of distance less than 3 is 3-colorable. This improves the main result of Borodin and Raspaud [Borodin, O. V., Raspaud, A.： A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, Ser. B, 88, 17-27 （2003）], and provides a new upper bound to their conjecture.
文摘In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G. This gives a positive support to a conjecture of Borodin and Raspaud which claims that each plane graph without 5-circuits and intersecting triangles is 3-colorable.
基金supported by the Zhejiang Provincial Natural Science Foundation ofChina (Grant No. Y6090699)National Natural Science Foundation of China (Grant No. 10971198)ZhejiangInnovation Project (Grant No. T200905)
文摘It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in it is adjacent to a 4-or a 5-cycle.This improves some known results in this direction.
基金supported by the National Natural Science Foundation of China(Nos 11271307,11171279,11101174)。
文摘Motivated by the connection with the genus of the corresponding link and its application on DNA polyhedral links,in this paper,we introduce a parameter s_(max)(G),which is the maximum number of circles of states of the link diagram D(G)corresponding to a plane(positive)graph G.We show that s_(max)(G)does not depend on the embedding of G and if G is a 4-edge-connected plane graph then s_(max)(G)is equal to the number of faces of G,which cover the results of S.Y.Liu and H.P.Zhang as special cases.
基金Supported by National Natural Science Foundation of China(No.10931003 and 11171160)the Doctoral Fund of Ministry of Education of China
文摘In 2003, Borodin and Raspaud proved that if G is a plane graph without 5-circuits and without triangles of distance less than four, then G is 3-colorable. In this paper, we prove that if G is a plane graph without 5- and 6-circuits and without triangles of distance less than 2, then G is 3-colorable.
基金This research is supported by the Postdoctoral Fund of China and the K.C.W. Education Fund of HongKong.
文摘A graph G is (a, b)-choosable for nonnegative integers a > b if for any given family {A(v)\v ε V(G)} of sets A(v) of cardinality a there exists a family {B(v)\v ε V(G)} of subsets B(v) A(v) of cardinality b such that B(u) B(v) =θ whenever uv E(G). It is Proved in this paper that every plane graph in which no two triangles share a common vertex is (4m, m)-choosable for every nonnegative integer m.
基金supported by National Natural Science Foundation of China (Grant Nos. 10931003, 10801077)the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Grant No. 08KJB110008).
文摘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 give some upper bounds on linear chromatic number for plane graphs with respect to their girth, that improve some results of Raspaud and Wang (2009).
基金Supported by National Natural Science Foundation of China(Grant Nos.11471273 and 11561058)
文摘Cycle reversal had been shown as a powerful method to deal with the relation among orientations of a graph since it preserves the out-degree of each vertex and the connectivity of the orientations. A facial cycle reversal on an orientation of a plane graph is an operation that reverses all the directions of the edges of a directed facial cycle. An orientation of a graph is called an α-orientation if each vertex admits a prescribed out-degree. In this paper, we give an explicit formula for the minimum number of the facial cycle reversals needed to transform one α-orientation into another for plane graphs.
文摘网络遥测是一种新型的网络测量技术,具有实时性强、准确性高、开销低的特点。现有网络遥测技术存在无法收集多粒度网络数据、无法有效存储大量原始网络数据、无法快速提取及生成网络遥测信息、无法利用内核态及用户态特性设计网络遥测方案等问题。为此,提出了一种融合内核态及用户态的、基于遥测数据图和同步控制块的多粒度、可扩展、覆盖全网的网络遥测机制(a nEtwork telemetry mechAnism based on telemetry data Graph in kerneL and usEr mode,EAGLE)。EAGLE设计了一种能够收集多粒度数据且数据平面上灵活可控的网络遥测数据包结构,用于获取上层应用所需的数据。此外,为快速存储、查询、统计、聚合网络状态数据,实现网络遥测数据包所需遥测数据的快速提取与生成,EAGLE提出了一种基于遥测数据图及同步控制块的网络遥测信息生成方法。在此基础上,为了最大化网络遥测机制中网络遥测数据包的处理效率,EAGLE提出了融合内核态及用户态特性的网络遥测信息嵌入架构。在Open vSwitch上实现了EAGLE方案并进行了测试,测试结果表明,EAGLE能够收集多粒度数据并快速提取与生成遥测数据,且仅增加极少量的处理时延及资源占用率。
基金supported by the National Natural Science Foundation of China(1 0 0 0 1 0 35)
文摘The choice number of a graph G,denoted byχl(G) ,is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own listno matter whatthe lists are.In this paper,itis showed thatχl(G)≤ 3 for each plane graph of girth not less than 4 which contains no 6- ,7- and 9- cycles
文摘Using the linear space over the binary field that related to a graph G, a sufficient and necessary condition for the chromatic number of G is obtained.
文摘A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic chromatic index of G,denoted by Xa(G),is the smallest integer k such that G is acyclically edge k-colorable.In this paper,we show that if G is a plane graph without 4-,6-cycles and intersecting 3-cycles,△(G)≥9,then Xa(G)≤△(G)+1.
