共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003 相似文献
4.
Manouchehr Zaker 《Journal of Graph Theory》2008,58(2):110-122
In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11 . Next, we obtain an upper bound of the order of magnitude for the coloring number of a graph with small K2,t (as subgraph), where n is the order of the graph. Finally, we give some bounds for chromatic number in terms of girth and book size. These bounds improve the best known bound, in terms of order and girth, for the chromatic number of a graph when its girth is an even integer. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:110–122, 2008 相似文献
5.
The strong chromatic index of a class of graphs 总被引:1,自引:0,他引:1
Jianzhuan Wu 《Discrete Mathematics》2008,308(24):6254-6261
The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ′(G)≤6. Let H0 be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H0 and d(x)+d(y)≤5 for any edge xy of G then sχ′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs. 相似文献
6.
A star edge-coloring of a graph is a proper edge coloring such that every 2-colored connected subgraph of is a path of length at most 3. For a graph , let the list star chromatic index of , , be the minimum such that for any -uniform list assignment for the set of edges, has a star edge-coloring from . Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph is less than (resp. 3), then (resp. ). 相似文献
7.
Improved bounds for acyclic chromatic index of planar graphs 总被引:1,自引:0,他引:1
8.
Manouchehr Zaker 《Discrete Applied Mathematics》2007,155(18):2567-2572
The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number. 相似文献
9.
We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001 相似文献
10.
Let consist of all simple graphs on 2k vertices and edges. For a simple graph G and a positive integer , let denote the number of proper vertex colorings of G in at most colors, and let . We prove that and is the only extremal graph. We also prove that as . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 135–148, 2007 相似文献
11.
In this paper, we prove that any graph G with maximum degree , which is embeddable in a surface Σ of characteristic χ(Σ) ≤ 1 and satisfies , is class one. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 197–205, 2000 相似文献
12.
本文利用矩阵行的初等变换 ,采用递推的方法 ,求出了有限域 k上 n次一般线性群 GLn(k)和 n次特殊线性群 SLn(k)的阶 . 相似文献
13.
14.
We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index. 相似文献
15.
A strong edge coloring of a graph is an assignment of colors to the edges of such that two distinct edges are colored differently if their distance is at most two. The strong chromatic index of a graph , denoted by , is the minimum number of colors needed for a strong edge coloring of . A Halin graph is a plane graph constructed from a tree without vertices of degree two by connecting all leaves through a cycle . If a Halin graph is different from a certain necklace and any wheel , , then we prove that . 相似文献
16.
A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively. 相似文献
17.
Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χe(G), χef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χef(G) = χe(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
18.
19.
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 χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010 相似文献
20.
An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours. We show that for every , there exists a such that if G has maximum degree Δ and girth at least g then G admits an acyclic edge colouring with colours. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 511–533, 2017 相似文献