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.展开更多
网络遥测是一种新型的网络测量技术,具有实时性强、准确性高、开销低的特点。现有网络遥测技术存在无法收集多粒度网络数据、无法有效存储大量原始网络数据、无法快速提取及生成网络遥测信息、无法利用内核态及用户态特性设计网络遥测...网络遥测是一种新型的网络测量技术,具有实时性强、准确性高、开销低的特点。现有网络遥测技术存在无法收集多粒度网络数据、无法有效存储大量原始网络数据、无法快速提取及生成网络遥测信息、无法利用内核态及用户态特性设计网络遥测方案等问题。为此,提出了一种融合内核态及用户态的、基于遥测数据图和同步控制块的多粒度、可扩展、覆盖全网的网络遥测机制(a nEtwork telemetry mechAnism based on telemetry data Graph in kerneL and usEr mode,EAGLE)。EAGLE设计了一种能够收集多粒度数据且数据平面上灵活可控的网络遥测数据包结构,用于获取上层应用所需的数据。此外,为快速存储、查询、统计、聚合网络状态数据,实现网络遥测数据包所需遥测数据的快速提取与生成,EAGLE提出了一种基于遥测数据图及同步控制块的网络遥测信息生成方法。在此基础上,为了最大化网络遥测机制中网络遥测数据包的处理效率,EAGLE提出了融合内核态及用户态特性的网络遥测信息嵌入架构。在Open vSwitch上实现了EAGLE方案并进行了测试,测试结果表明,EAGLE能够收集多粒度数据并快速提取与生成遥测数据,且仅增加极少量的处理时延及资源占用率。展开更多
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}.展开更多
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.展开更多
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 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.
文摘网络遥测是一种新型的网络测量技术,具有实时性强、准确性高、开销低的特点。现有网络遥测技术存在无法收集多粒度网络数据、无法有效存储大量原始网络数据、无法快速提取及生成网络遥测信息、无法利用内核态及用户态特性设计网络遥测方案等问题。为此,提出了一种融合内核态及用户态的、基于遥测数据图和同步控制块的多粒度、可扩展、覆盖全网的网络遥测机制(a nEtwork telemetry mechAnism based on telemetry data Graph in kerneL and usEr mode,EAGLE)。EAGLE设计了一种能够收集多粒度数据且数据平面上灵活可控的网络遥测数据包结构,用于获取上层应用所需的数据。此外,为快速存储、查询、统计、聚合网络状态数据,实现网络遥测数据包所需遥测数据的快速提取与生成,EAGLE提出了一种基于遥测数据图及同步控制块的网络遥测信息生成方法。在此基础上,为了最大化网络遥测机制中网络遥测数据包的处理效率,EAGLE提出了融合内核态及用户态特性的网络遥测信息嵌入架构。在Open vSwitch上实现了EAGLE方案并进行了测试,测试结果表明,EAGLE能够收集多粒度数据并快速提取与生成遥测数据,且仅增加极少量的处理时延及资源占用率。
文摘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}.
基金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.
基金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.
