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.展开更多
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 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 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).展开更多
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.展开更多
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.展开更多
基金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.
文摘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 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.
基金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).
基金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.
文摘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.
