共查询到20条相似文献,搜索用时 203 毫秒
1.
An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a′(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. It was conjectured that a′(G)≤Δ+2 for any simple graph G with maximum degree Δ. In this paper, we prove that if G is a planar graph, then a′(G)≤Δ+7. This improves a result by Basavaraju et al. [M. Basavaraju, L.S. Chandran, N. Cohen, F. Havet, T. Müller, Acyclic edge-coloring of planar graphs, SIAM J. Discrete Math. 25 (2011) 463–478], which says that every planar graph G satisfies a′(G)≤Δ+12. 相似文献
2.
3.
4.
Kelly, Kühn and Osthus conjectured that for any ?≥4 and the smallest number k≥3 that does not divide ?, any large enough oriented graph G with δ+(G),δ−(G)≥⌊|V(G)|/k⌋+1 contains a directed cycle of length ?. We prove this conjecture asymptotically for the case when ? is large enough compared to k and k≥7. The case when k≤6 was already settled asymptotically by Kelly, Kühn and Osthus. 相似文献
5.
Mustapha Chellali Teresa W. Haynes Stephen T. Hedetniemi Alice McRae 《Discrete Applied Mathematics》2013
A subset S⊆V in a graph G=(V,E) is a [j,k]-set if, for every vertex v∈V?S, j≤|N(v)∩S|≤k for non-negative integers j and k, that is, every vertex v∈V?S is adjacent to at least j but not more than k vertices in S. In this paper, we focus on small j and k, and relate the concept of [j,k]-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G, the restrained domination number is equal to the domination number of G. 相似文献
7.
Consider a graph G with a minimal edge cut F and let G1, G2 be the two (augmented) components of G−F. A long-open question asks under which conditions the crossing number of G is (greater than or) equal to the sum of the crossing numbers of G1 and G2—which would allow us to consider those graphs separately. It is known that crossing number is additive for |F|∈{0,1,2} and that there exist graphs violating this property with |F|≥4. In this paper, we show that crossing number is additive for |F|=3, thus closing the final gap in the question. 相似文献
8.
We prove that if G is a finite simple group which is the unit group of a ring, then G is isomorphic to: (a) a cyclic group of order 2; or (b) a cyclic group of prime order 2k−1 for some k; or (c) a projective special linear group PSLn(F2) for some n≥3. Moreover, these groups do all occur as unit groups. We deduce this classification from a more general result, which holds for groups G with no non-trivial normal 2-subgroup. 相似文献
9.
10.
12.
13.
14.
In this note we study distance-regular graphs with a small number of vertices compared to the valency. We show that for a given α>2, there are finitely many distance-regular graphs Γ with valency k, diameter D≥3 and v vertices satisfying v≤αk unless (D=3 and Γ is imprimitive) or (D=4 and Γ is antipodal and bipartite). We also show, as a consequence of this result, that there are finitely many distance-regular graphs with valency k≥3, diameter D≥3 and c2≥εk for a given 0<ε<1 unless (D=3 and Γ is imprimitive) or (D=4 and Γ is antipodal and bipartite). 相似文献
15.
Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d be an integer at least 3, and let G be a graph with maximum degree d. If G does not contain Kd+1 as a subgraph, then G has a d-coloring in which one color class has size α(G). Here α(G) denotes the independence number of G. We give a unified proof of Brooks’ theorem and Catlin’s theorem. 相似文献
16.
17.
Jean-Stéphane Dhersin Fabian Freund Arno Siri-Jégousse Linglong Yuan 《Stochastic Processes and their Applications》2013
In this paper, we consider Beta(2−α,α) (with 1<α<2) and related Λ-coalescents. If T(n) denotes the length of a randomly chosen external branch of the n-coalescent, we prove the convergence of nα−1T(n) when n tends to ∞, and give the limit. To this aim, we give asymptotics for the number σ(n) of collisions which occur in the n-coalescent until the end of the chosen external branch, and for the block counting process associated with the n-coalescent. 相似文献
18.
We consider G=Γ×S1 with Γ being a finite group, for which the complete Euler ring structure in U(G) is described. The multiplication tables for Γ=D6, S4 and A5 are provided in the Appendix. The equivariant degree for G-orthogonal maps is constructed using the primary equivariant degree with one free parameter. We show that the G-orthogonal degree extends the degree for G-gradient maps (in the case of G=Γ×S1) introduced by G?ba in [K. G?ba, W. Krawcewicz, J. Wu, An equivariant degree with applications to symmetric bifurcation problems I: Construction of the degree, Bull. London. Math. Soc. 69 (1994) 377–398]. The computational results obtained are applied to a Γ-symmetric autonomous Newtonian system for which we study the existence of 2π-periodic solutions. For some concrete cases, we present the symmetric classification of the solution set for the systems considered. 相似文献
19.
Let T be a tree with s ends and f,g be continuous maps from T to T with f°g=g°f. In this note we show that if there exists a positive integer m≥2 such that gcd(m,l)=1 for any 2≤l≤s and f,g share a periodic point which is a km-periodic point of f for some positive integer k, then the topological entropy of f°g is positive. 相似文献
20.
The paper deals with the radially symmetric solutions of ut=Δu+um(x,t)vn(0,t), vt=Δv+up(0,t)vq(x,t), subject to null Dirichlet boundary conditions. For the blow-up classical solutions, we propose the critical exponents for non-simultaneous blow-up by determining the complete and optimal classification for all the non-negative exponents: (i) There exist initial data such that u (v) blows up alone if and only if m>p+1 (q>n+1), which means that any blow-up is simultaneous if and only if m≤p+1, q≤n+1. (ii) Any blow-up is u (v) blowing up with v (u) remaining bounded if and only if m>p+1, q≤n+1 (m≤p+1, q>n+1). (iii) Both non-simultaneous and simultaneous blow-up may occur if and only if m>p+1, q>n+1. Moreover, we consider the blow-up rate and set estimates which were not obtained in the previously known work for the same model. 相似文献