共查询到20条相似文献,搜索用时 62 毫秒
1.
The Entire Coloring of Series-Parallel Graphs 总被引:2,自引:0,他引:2
Jian-liangWu Yu-liangWu 《应用数学学报(英文版)》2005,21(1):61-66
The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6. 相似文献
2.
Some results on spanning trees 总被引:2,自引:0,他引:2
Some structures of spanning trees with many or less leaves in a connected graph are determined.We show(1) a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and(2) a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ(G) =Δ(T) and the number of leaves of T is not greater than n D(G)+1,where D(G) is the diameter of G. 相似文献
3.
Daniel W. Cranston 《Graphs and Combinatorics》2009,25(1):35-40
The total graph T(G) of a multigraph G has as its vertices the set of edges and vertices of G and has an edge between two vertices if their corresponding elements are either adjacent or incident in G. We show that if G has maximum degree Δ(G), then T(G) is (2Δ(G) − 1)-choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for
Δ(G) > 3 was , by Borodin et al. When Δ(G) = 4, our algorithm gives a better upper bound. When Δ(G)∈{3,5,6}, our algorithm matches the best known bound. However, because our algorithm is significantly simpler, it runs in
linear time (unlike the algorithm of Borodin et al.). 相似文献
4.
A. O. Ivanova 《Journal of Applied and Industrial Mathematics》2011,5(2):221-230
The trivial lower bound for the 2-distance chromatic number χ
2(G) of a graph G with maximum degree Δ is Δ + 1. There are available some examples of the graphs with girth g ≤ 6 that have arbitrarily large Δ and χ
2(G) ≥ Δ + 2. In the paper we improve the known restrictions on Δ and g under which a planar graph G has χ
2(G) = Δ + 1. 相似文献
5.
Let G be an outerplanar graph with maximum degree △. Let χ(G^2) and A(G) denote the chromatic number of the square and the L(2, 1)-labelling number of G, respectively. In this paper we prove the following results: (1) χ(G^2) = 7 if △= 6; (2) λ(G) ≤ △ +5 if △ ≥ 4, and ),(G)≤ 7 if △ = 3; and (3) there is an outerplanar graph G with △ = 4 such that )λ(G) = 7. These improve some known results on the distance two labelling of outerplanar graphs. 相似文献
6.
Let p be a positive integer and G = (V, E) be a simple graph. A p-dominating set of G is a subset D í V{D\,{\subseteq}\, V} such that every vertex not in D has at least p neighbors in D. The p-domination number of G is the minimum cardinality of a p-dominating set of G. The p-bondage number of a graph G with (ΔG) ≥ p is the minimum cardinality among all sets of edges B í E{B\subseteq E} for which γ
p
(G − B) > γ
p
(G). For any integer p ≥ 2 and tree T with (ΔT) ≥ p, this paper shows that 1 ≤ b
p
(T) ≤ (ΔT) − p + 1, and characterizes all trees achieving the equalities. 相似文献
7.
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1.
This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation
of Shandong Province (Grant No. Y2008A20). 相似文献
8.
A vertex coloring of a graph G is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number χ
i
(G) of the colors required for an injective coloring of a graph G is clearly not less than the maximum degree Δ(G) of G. There exist planar graphs with girth g ≥ 6 and χ
i
= Δ+1 for any Δ ≥ 2. We prove that every planar graph with Δ ≥ 18 and g ≥ 6 has χ
i
≤ Δ + 1. 相似文献
9.
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper,
it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs. 相似文献
10.
Sergey Bereg 《Graphs and Combinatorics》2009,25(2):139-144
We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning
trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning
trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G.
A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph
G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice. 相似文献
11.
The Linear 2-Arboricity of Planar Graphs 总被引:2,自引:0,他引:2
Let G be a planar graph with maximum degree Δ and girth g. The linear 2-arboricity la
2(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. We prove that (1) la
2(G)≤⌈(Δ+1)/2⌉+12; (2) la
2(G)≤⌈(Δ+1)/2⌉+6 if g≥4; (3) la
2(G)≤⌈(Δ+1)/2⌉+2 if g≥5; (4) la
2(G)≤⌈(Δ+1)/2⌉+1 if g≥7.
Received: June 28, 2001 Final version received: May 17, 2002
Acknowledgments. This work was done while the second and third authors were visiting the Institute of Mathematics, Academia Sinica, Taipei.
The financial support provided by the Institute is greatly appreciated. 相似文献
12.
Suppose that G is a planar graph with maximum degree Δ. In this paper it is proved that G is total-(Δ + 2)-choosable if (1) Δ ≥ 7 and G has no adjacent triangles (i.e., no two triangles are incident with a common edge); or (2) Δ ≥ 6 and G has no intersecting triangles (i.e., no two triangles are incident with a common vertex); or (3) Δ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}. 相似文献
13.
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 prove that every graph G with girth g(G) and maximum degree Δ(G) that can be embedded in a surface of nonnegative characteristic has lc(G) = Δ(2G )+ 1 if there is a pair (Δ, g) ∈ {(13, 7), (9, 8), (7, 9), (5, 10), (3, 13)} such that G s... 相似文献
14.
On total chromatic number of planar graphs without 4-cycles 总被引:5,自引:0,他引:5
Min-le SHANGGUAN 《中国科学A辑(英文版)》2007,50(1):81-86
Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture. 相似文献
15.
Tiziana Calamoneri Emanuele G. Fusco Richard B. Tan Paola Vocca 《Mathematical Methods of Operations Research》2009,69(2):307-321
An L(h, 1, 1)-labeling of a graph is an assignment of labels from the set of integers {0, . . . , λ} to the nodes of the graph such
that adjacent nodes are assigned integers of at least distance h ≥ 1 apart and all nodes of distance three or less must be assigned different labels. The aim of the L(h, 1, 1)-labeling problem is to minimize λ, denoted by λ
h, 1, 1 and called span of the L(h, 1, 1)-labeling. As outerplanar graphs have bounded treewidth, the L(1, 1, 1)-labeling problem on outerplanar graphs can be exactly solved in O(n
3), but the multiplicative factor depends on the maximum degree Δ and is too big to be of practical use. In this paper we give
a linear time approximation algorithm for computing the more general L(h, 1, 1)-labeling for outerplanar graphs that is within additive constants of the optimum values.
This research is partially supported by the European Research Project Algorithmic Principles for Building Efficient Overlay Computers (AEOLUS) and was done during the visit of Richard B. Tan at the Department of Computer Science, University of Rome “Sapienza”, supported
by a visiting fellowship from the University of Rome “Sapienza”. 相似文献
16.
A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total
coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k. 相似文献
17.
A proper edge colouring of a graph G is neighbour-distinguishing provided that it distinguishes adjacent vertices by sets of colours of their incident edges.
It is proved that for any planar bipartite graph G with Δ(G)≥12 there is a neighbour-distinguishing edge colouring of G using at most Δ(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered. 相似文献
18.
The trivial lower bound for the 2-distance chromatic number χ
2(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ
2 = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ
2(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 23, which strengthens a similar result by O. V. Borodin, A. O. Ivanova, and T. K. Neustroeva (2004) and Z. Dvořák, R. Škrekovski,
and M. Tancer (2008) for g ≥ 24. 相似文献
19.
WANGWEIFAN ZHANGKEMIN 《高校应用数学学报(英文版)》1997,12(4):455-462
A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g. 相似文献
20.
Ear Decompositions of Matching Covered Graphs 总被引:3,自引:0,他引:3
G different from and has at least Δ edge-disjoint removable ears, where Δ is the maximum degree of G. This shows that any matching covered graph G has at least Δ! different ear decompositions, and thus is a generalization of the fundamental theorem of Lovász and Plummer
establishing the existence of ear decompositions. We also show that every brick G different from and has Δ− 2 edges, each of which is a removable edge in G, that is, an edge whose deletion from G results in a matching covered graph. This generalizes a well-known theorem of Lovász. We also give a simple proof of another
theorem due to Lovász which says that every nonbipartite matching covered graph has a canonical ear decomposition, that is,
one in which either the third graph in the sequence is an odd-subdivision of or the fourth graph in the sequence is an odd-subdivision of . Our method in fact shows that every nonbipartite matching covered graph has a canonical ear decomposition which is optimal,
that is one which has as few double ears as possible. Most of these results appear in the Ph. D. thesis of the first author
[1], written under the supervision of the second author.
Received: November 3, 1997 相似文献