共查询到20条相似文献,搜索用时 312 毫秒
1.
2.
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. 相似文献
3.
Albert Guan 《Discrete Mathematics》2009,309(20):6044-6047
Given a (possibly improper) edge colouring F of a graph G, a vertex colouring of G is adapted toF if no colour appears at the same time on an edge and on its two endpoints. A graph G is called (for some positive integer k) if for any list assignment L to the vertices of G, with |L(v)|≥k for all v, and any edge colouring F of G, G admits a colouring c adapted to F where c(v)∈L(v) for all v. This paper proves that a planar graph G is adaptably 3-choosable if any two triangles in G have distance at least 2 and no triangle is adjacent to a 4-cycle. 相似文献
4.
Timothy J. Hetherington 《Discrete Mathematics》2009,309(8):2153-2165
It is proved that if G is a plane embedding of a K4-minor-free graph with maximum degree Δ, then G is entirely 7-choosable if Δ≤4 and G is entirely (Δ+2)-choosable if Δ≥5; that is, if every vertex, edge and face of G is given a list of max{7,Δ+2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if G is a plane embedding of a K2,3-minor-free graph or a -minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely (Δ+4)-colourable, holds if G is a plane embedding of a K4-minor-free graph, a K2,3-minor-free graph or a -minor-free graph. 相似文献
5.
Daqing Yang 《Discrete Mathematics》2009,309(13):4614-4623
Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,
- 1.
- if and then or (fraternity);
- 2.
- if and then (transitivity).
6.
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). 相似文献
7.
Total colorings and list total colorings of planar graphs without intersecting 4-cycles 总被引:1,自引:0,他引:1
Suppose that G is a planar graph with maximum degree Δ and without intersecting 4-cycles, that is, no two cycles of length 4 have a common vertex. Let χ″(G), and denote the total chromatic number, list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that χ″(G)=Δ+1 if Δ≥7, and and if Δ(G)≥8. Furthermore, if G is a graph embedded in a surface of nonnegative characteristic, then our results also hold. 相似文献
8.
Thomas Böhme 《Discrete Mathematics》2006,306(7):666-669
We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L3(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number kG such that for every i?kG the i-iterated line graph of G is -linked. Since the degree of Li(G) is even, the result is best possible. 相似文献
9.
Let G be an undirected graph that is neither a path nor a cycle. Clark and Wormald [L.H. Clark, N.C. Wormald, Hamiltonian-like indices of graphs, ARS Combinatoria 15 (1983) 131-148] defined hc(G) to be the least integer m such that the iterated line graph Lm(G) is Hamilton-connected. Let be the diameter of G and k be the length of a longest path whose internal vertices, if any, have degree 2 in G. In this paper, we show that . We also show that κ3(G)≤hc(G)≤κ3(G)+2 where κ3(G) is the least integer m such that Lm(G) is 3-connected. Finally we prove that hc(G)≤|V(G)|−Δ(G)+1. These bounds are all sharp. 相似文献
10.
Margit Voigt 《Discrete Mathematics》2009,309(15):4926-4930
Let G=G(V,E) be a simple graph, L a list assignment with |L(v)|=Δ(G)∀v∈V and W⊆V an independent subset of the vertex set. Define to be the minimum distance between two vertices of W. In this paper it is shown that if G is 2-connected with Δ(G)=3 and G is not K4 then every precoloring of W is extendable to a proper list coloring of G provided that d(W)≥6. An example shows that the bound is sharp. This result completes the investigation of precoloring extensions for graphs with |L(v)|=Δ(G) for all v∈V where the precolored set W is an independent set. 相似文献
11.
Acyclic edge colouring of planar graphs without short cycles 总被引:1,自引:0,他引:1
Mieczys?aw Borowiecki 《Discrete Mathematics》2010,310(9):1445-2495
Let G=(V,E) be any finite graph. A mapping C:E→[k] is called an acyclic edgek-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges which have colour i or j, is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G, denoted by .In 2001, Alon et al. conjectured that for any graph G it holds that ; here Δ(G) stands for the maximum degree of G.In this paper we prove this conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4,6,8 and 9. We also show that if G is planar with girth at least 6. Moreover, we find an upper bound for the acyclic chromatic index of planar graphs without cycles of length 4. Namely, we prove that if G is such a graph, then . 相似文献
12.
Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γk(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number irk(G). The authors prove that if an irk-set X is a k-independent set of G, then , and that for k?2, if irk(G)=1, if irk(G) is odd, and if irk(G) is even, which generalize some known results. 相似文献
13.
Dong Chen 《Discrete Applied Mathematics》2007,155(18):2585-2593
The (2,1)-total labelling number of a graph G is the width of the smallest range of integers that suffices to label the vertices and the edges of G such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper we prove that if G is an outerplanar graph with maximum degree Δ(G), then if Δ(G)?5, or Δ(G)=3 and G is 2-connected, or Δ(G)=4 and G contains no intersecting triangles. 相似文献
14.
C.N. Campos 《Discrete Applied Mathematics》2007,155(5):585-597
The total chromatic number χT(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. The Total Colouring Conjecture (TCC) states that for every simple graph G, χT(G)?Δ(G)+2. This work verifies the TCC for powers of cycles even and 2<k<n/2, showing that there exists and can be polynomially constructed a (Δ(G)+2)-total colouring for these graphs. 相似文献
15.
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. 相似文献
16.
José J. Ramón Marí 《Advances in Mathematics》2010,224(6):2237-2268
In this paper we give a detailed analysis of the interaction between homological self-correspondences of the general fibre Y/k(t) of the Lefschetz fibration of a Lefschetz pencil on a smooth projective variety X/k, and the Leray filtration of ρ. We derive the result that, if the standard conjecture B(Y) holds, then the operator is algebraic, where is defined as the inverse of L on LPn−1(X) and 0 on LkPj(X) for (1,n−1)≠(k,j); in the course of our proof we see that, under the above assumption, the Künneth projectors for i≠n−1,n,n+1 are algebraic. 相似文献
17.
18.
Improved bounds on coloring of graphs 总被引:1,自引:0,他引:1
Sokol Ndreca 《European Journal of Combinatorics》2012,33(4):592-609
19.
Francesca Fiorenzi 《Discrete Applied Mathematics》2011,159(17):2045-2049
20.
A k-dimensional box is the cartesian product R1×R2×?×Rk where each Ri is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R1×R2×?×Rk where each Ri is a closed interval on the real line of the form [ai,ai+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G)≤t+⌈log(n−t)⌉−1 and , where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds.F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, and , where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then and this bound is tight. We also show that if G is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , s≥0, then , where χ(G) is the chromatic number of G. 相似文献