共查询到20条相似文献,搜索用时 92 毫秒
1.
Andrzej Czygrinow 《Discrete Mathematics》2004,286(3):219-223
For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χs(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χs(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n0(d,ε) satisfy χs(G)?ζ(ε)Δ(G)2, where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24). 相似文献
2.
Planar graphs without 5-cycles or without 6-cycles 总被引:1,自引:0,他引:1
Let G be a planar graph without 5-cycles or without 6-cycles. In this paper, we prove that if G is connected and δ(G)≥2, then there exists an edge xy∈E(G) such that d(x)+d(y)≤9, or there is a 2-alternating cycle. By using the above result, we obtain that (1) its linear 2-arboricity , (2) its list total chromatic number is Δ(G)+1 if Δ(G)≥8, and (3) its list edge chromatic number is Δ(G) if Δ(G)≥8. 相似文献
3.
Equitable colorings of Kronecker products of graphs 总被引:1,自引:0,他引:1
Wu-Hsiung Lin 《Discrete Applied Mathematics》2010,158(16):1816-1826
For a positive integer k, a graph G is equitably k-colorable if there is a mapping f:V(G)→{1,2,…,k} such that f(x)≠f(y) whenever xy∈E(G) and ||f−1(i)|−|f−1(j)||≤1 for 1≤i<j≤k. The equitable chromatic number of a graph G, denoted by χ=(G), is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by , is the minimum t such that G is equitably k-colorable for k≥t. The current paper studies equitable chromatic numbers of Kronecker products of graphs. In particular, we give exact values or upper bounds on χ=(G×H) and when G and H are complete graphs, bipartite graphs, paths or cycles. 相似文献
4.
A structural theorem for planar graphs with some applications 总被引:1,自引:0,他引:1
Huiyu ShengYingqian Wang 《Discrete Applied Mathematics》2011,159(11):1183-1187
In this note, we prove a structural theorem for planar graphs, namely that every planar graph has one of four possible configurations: (1) a vertex of degree 1, (2) intersecting triangles, (3) an edge xy with d(x)+d(y)≤9, (4) a 2-alternating cycle. Applying this theorem, new moderate results on edge choosability, total choosability, edge-partitions and linear arboricity of planar graphs are obtained. 相似文献
5.
The total chromatic number χT(G) of a graph G is the least number of colors needed to color the vertices and the edges of G such that no adjacent or incident elements receive the same color. The Total Coloring Conjecture(TCC) states that for every simple graph G, χT(G)≤Δ(G)+2. In this paper, we show that χT(G)=Δ(G)+1 for all pseudo-Halin graphs with Δ(G)=4 and 5. 相似文献
6.
Diego Scheide 《Discrete Mathematics》2009,309(15):4920-4925
Two of the basic results on edge coloring are Vizing’s Theorem [V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian); V.G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965) 29-39 (in Russian). English translation in Cybernetics 1 32-41], which states that the chromatic index χ′(G) of a (multi)graph G with maximum degree Δ(G) and maximum multiplicity μ(G) satisfies Δ(G)≤χ′(G)≤Δ(G)+μ(G), and Holyer’s Theorem [I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720], which states that the problem of determining the chromatic index of even a simple graph is NP-hard. Hence, a good characterization of those graphs for which Vizing’s upper bound is attained seems to be unlikely. On the other hand, Vizing noticed in the first two above-cited references that the upper bound cannot be attained if Δ(G)=2μ(G)+1≥5. In this paper we discuss the problem: For which values Δ,μ does there exist a graph G satisfying Δ(G)=Δ, μ(G)=μ, and χ′(G)=Δ+μ. 相似文献
7.
Xin Min Hou 《数学学报(英文版)》2012,28(11):2161-2168
A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al. 相似文献
8.
Michel Las Vergnas 《Discrete Mathematics》1976,15(1):27-39
The main result of this paper is the following theorem: Let G = (X,E) be a digraph without loops or multiple edges, |X| ?3, and h be an integer ?1, if G contains a spanning arborescence and if d+G(x)+d?G(x)+d?G(y)+d?G(y)? 2|X |?2h?1 for all x, y?X, x ≠ y, non adjacent in G, then G contains a spanning arborescence with ?h terminal vertices. A strengthening of Gallai-Milgram's theorem is also proved. 相似文献
9.
Let G be a simple graph on n vertices. In this paper, we prove that if G satisfies the condition that d(x)+d(y)≥n for each xy∈E(G), then G has no nowhere-zero 3-flow if and only if G is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices. 相似文献
10.
J.A. MacDougall 《Discrete Mathematics》2008,308(13):2756-2763
An edge-magic total labeling on G is a one-to-one map λ from V(G)∪E(G) onto the integers 1,2,…,|V(G)∪E(G)| with the property that, given any edge (x,y), λ(x)+λ(x,y)+λ(y)=k for some constant k. The labeling is strong if all the smallest labels are assigned to the vertices. Enomoto et al. proved that a graph admitting a strong labeling can have at most 2|V(G)|-3 edges. In this paper we study graphs of this maximum size. 相似文献
11.
Let G be a planar graph of maximum degree 6. In this paper we prove that if G does not contain either a 6-cycle, or a 4-cycle with a chord, or a 5- and 6-cycle with a chord, then χ′(G)=6, where χ′(G) denotes the chromatic index of G. 相似文献
12.
W.T Tutte 《Journal of Combinatorial Theory, Series B》1974,16(2):168-174
A construction is given for two non-isomorphic graphs G and H such that χ(G; x, y) = χ(H; x, y). The two graphs can be made strict, and even 5-connected. 相似文献
13.
Ali Behtoei Behnaz Omoomi 《Discrete Applied Mathematics》2011,159(18):2214-2221
Let c be a proper k-coloring of a connected graph G and Π=(C1,C2,…,Ck) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple cΠ(v):=(d(v,C1),d(v,C2),…,d(v,Ck)), where d(v,Ci)=min{d(v,x)|x∈Ci},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χL(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χL(KG(n,2))=n−1 for all n≥5. Then, we prove that χL(KG(n,k))≤n−1, when n≥k2. Moreover, we present some bounds for the locating chromatic number of odd graphs. 相似文献
14.
Ioan Tomescu 《Discrete Applied Mathematics》2010,158(15):1714-1717
The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D′(G)=∑x∈V(G)d(x)∑y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K1,n−1,BS(n−3,1) and K1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K1,n−3 and K1,1 with central vertices joined by an edge. 相似文献
15.
16.
Toru Kojima 《Discrete Mathematics》2008,308(7):1282-1295
The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)-f(y)|:xy∈E(G)} taken over all proper numberings f of G. The strong product of two graphs G and H, written as G(SP)H, is the graph with vertex set V(G)×V(H) and with (u1,v1) adjacent to (u2,v2) if one of the following holds: (a) u1 and v1 are adjacent to u2 and v2 in G and H, respectively, (b) u1 is adjacent to u2 in G and v1=v2, or (c) u1=u2 and v1 is adjacent to v2 in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by D(G). Let d be a positive integer and let x,y be two vertices of G. Let denote the set of vertices v so that the distance between x and v in G is at most d. We define δd(G) as the minimum value of over all vertices x of G. Let denote the set of vertices z such that the distance between x and z in G is at most d-1 and z is adjacent to y. We denote the larger of and by . We define η(G)=1 if G is complete and η(G) as the minimum of over all pair of vertices x,y of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if δD(H)(G)?B(G)D(H)+1 and B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉, then B(G(SP)H)=B(G)|V(H)|+B(H). Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs. 相似文献
17.
A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χl(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χl(G) and χl(H). On the other hand, we prove that χl(G×H)?min{χl(G)+col(H),col(G)+χl(H)}-1 and construct examples of graphs G and H for which our bound is tight. 相似文献
18.
Let denote the maximum average degree (over all subgraphs) of G and let χi(G) denote the injective chromatic number of G. We prove that if , then χi(G)≤Δ(G)+1; and if , then χi(G)=Δ(G). Suppose that G is a planar graph with girth g(G) and Δ(G)≥4. We prove that if g(G)≥9, then χi(G)≤Δ(G)+1; similarly, if g(G)≥13, then χi(G)=Δ(G). 相似文献
19.
In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χcg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χcg(G)≤2χa(G)(χa(G)+1), where χa(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles. 相似文献
20.
Mostafa Blidia 《Discrete Mathematics》2008,308(10):1785-1791
We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+βv(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and βv(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs. 相似文献