Improved upper bounds on acyclic edge colorings

An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors.The acyclic chromatic index of a graph G,denoted by a′(G),is the minimum number k such that there is an acyclic edge coloring using k colors.It is known that a′(G)≤16△for every graph G where △denotes the maximum degree of G.We prove that a′(G)13.8△for an arbitrary graph G.We also reduce the upper bounds of a′(G)to 9.8△and 9△with girth 5 and 7,respectively.     

CORRECTION TO “ON THE PROBLEM OF BEST CONVERGENCE RATES OF DENSITY ESTIMATES

The assertion of Th.1 in[1]should be replaced bylimsup n→∞ a_nn~(k/(2k m)=∞.(A)Since the proof of Th.1 in[1]is somewhat in error,we give here a sketch ofproof of(A).Choose f∈C_ka with f(x)≥a>0 for ‖x‖≤ε>0,and define h_δ(x)=f(x) e_(kδ)(x),where e_(kδ)(x),as well as d and C_(kα)~(n)(d) to appear in the following,are thesame as in[1].Choose ■>0 so that h_δ∈C_(kα) for δ∈(0,■).For each δ in(0,■),thereexists an integer n such that h_δ∈C_(kα)~(n)(d).Hence an integer N can be found such that     

Neighbor Sum Distinguishing Colorings of Graphs with Maximum Average Degree Less Than 37/12

Let G be a graph and let its maximum degree and maximum average degree be denoted byΔ(G) and mad(G), respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E(G), the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by χ'∑≠(G). Flandrin et al. proposed the following conjecture thatχ'∑(G) ≤Δ(G) + 2 for any connected graph with at least 3 vertices and G≠C_5. In this paper, we prove that the conjecture holds for a normal graph with mad(G) 37/12 and Δ(G) ≥ 7.     

Zeros of Monomial Brauer Characters

Let G be a finite group and p be a fixed prime. A p-Brauer character of G is said to be monomial if it is induced from a linear p-Brauer character of some subgroup(not necessarily proper) of G. Denote by IBr_m(G) the set of irreducible monomial p-Brauer′characters of G. Let H = G′O~p′(G) be the smallest normal subgroup such that G/H is an abelian p′-group. Suppose that g ∈ G is a p-regular element and the order of gH in the factor group G/H does not divide |IBr_m(G)|. Then there exists ? ∈ IBr_m(G) such that ?(g) = 0.     

Problems Concerning Embeddings of Manifolds

Very little is known in general about estimating the smallest integer l such that a manifold Mn emheds in Rn+k +l if it immerses in Rn+k. Indeed there are relatively few examples where k and l can be estimated accurately. There are old examples for which l is known to be arbitrarily Iarge; for those examples l can grow like logn and there are recent examples where l can grow linearly with n. The main difficulty in resolving questions of this kind is that the only general methods known for proving non-embedding and non-immersion results involve doing calculations with characteristic classes and the estimates that they give are very similar for the two problems. In this paper an account is given of various methods that can be used to study examples.     

A result on quasi k-connected graphs

Let G be a k-connected graph, and T be a subset of V(G)If G- T is not connected,then T is said to be a cut-set of GA k-cut-set T of G is a cut-set of G with |T | = kLet T be a k-cut-set of a k-connected graph GIf G- T can be partitioned into subgraphs G1 and G2 such that |G1| ≥ 2, |G2| ≥ 2, then we call T a nontrivial k-cut-set of GSuppose that G is a(k- 1)-connected graph without nontrivial(k- 1)-cut-setThen we call G a quasi k-connected graphIn this paper, we prove that for any integer k ≥ 5, if G is a k-connected graph without K-4, then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least|V(G)|2edges of G such that the contraction of every member of them results in a quasi k-connected graph.     

Bipartition of graph under degree constraints

Let G be a graph, let s be a positive integer, and let X be a subset of V(G). Denote δ(X) to be the minimum degree of the subgraph G[X] induced by X. A partition(X, Y) of V(G) is called s-good if min{δ(X), δ(Y)} s. In this paper, we strengthen a result of Maurer and a result of Arkin and Hassin, and prove that for any positive integer k with 2 k |V(G)|- 2, every connected graph G with δ(G) 2 admits a1-good partition(X, Y) such that |X| = k and |Y| = |V(G)|- k, and δ(X) + δ(Y) δ(G)- 1.     

Some Class 1 Graphs on g_c-colorings

An edge-coloring of a graph G is an assignment of colors to all the edges of G.A g_c-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least g(v)times.The maximum integer k such that G has a g_c-coloring with k colors is called the g_c-chromatic index of G and denoted by χ'g_c(G).In this paper,we extend a result on edge-covering coloring of Zhang and Liu in 2011,and give a new sufficient condition for a simple graph G to satisfy χ'g_c(G)=δ_g(G),where δ_g(G)=min_(v∈V(G) {└d(v)/g(v)┘ }).     

3,4跳图的平面性

For a graph G of size ε≥1 and its edge-induced subgraphs H1 and H2 of size r(1≤r≤ε), H1 is said to be obtained from H2 by an edge jump if there exist four distinct vertices u,v,w and x in G such that (u,v)∈E(H2), (w,x)∈ E(G)-E(H2) and H1=H2-(u,v)+(w,x). In this article, the r-jump graphs (r≥3) are discussed. A graph H is said to be an r-jump graph of G if its vertices correspond to the edge induced graph of size r in G and two vertices are adjacent if and only if one of the two corresponding subgraphs can be obtained from the other by an edge jump. For k≥2, the k-th iterated r-jump graph Jrk(G) is defined as Jr(Jrk-1(G)), where Jr1(G)=Jr(G).An infinite sequence{Gi} of graphs is planar if every graph Gi is planar. It is shown that there does not exist a graph G for which the sequence {J3k(G)} is planar, where k is any positive integer. Meanwhile,lim gen(J3k(G))=∞,where gen(G) denotes the genus of a graph G, if the sequencek→∞J3k(G) is defined for every positive integer k. As for the 4-jump gra     

Distributing pairs of vertices on Hamiltonian cycles

Let G be a graph of order n with minimum degree δ(G)≥n/2+1. Faudree and Li(2012) conjectured that for any pair of vertices x and y in G and any integer 2≤k≤n/2, there exists a Hamiltonian cycle C such that the distance between x and y on C is k. In this paper, we prove that this conjecture is true for graphs of sufficiently large order. The main tools of our proof are the regularity lemma of Szemer′edi and the blow-up lemma of Koml′os et al.(1997).     

A SOLUTION TO ONE OF KANO''''S CONJECTURES CONCERNING k-th MAXIMAL SPANNING TREES

Let (G) be the collection of all spanning trees of a connected and weighted graph G,and F_1, F_2,…,F_m the partition of (G) such that F_i is the set of i-th maximal spanning trees of G.Kano conjectured that for any A∈F_1 and every integer k,1≤k≤m,there exists T∈F_k such that|T/A| k—l.This paper gives the conjecture a very simple proof,and related results.     

GRAPHS ISOMORPHIC TO SUBGRAPHS OF THEIR ITERATED LINE GRAPHS

A graph G is said to be embeddable into a graph H,if there is an isomorphism of G into asubgraph of H.It is shown in this paper that every unicycle or tree which is neither a path nor K_(1,3)embeds in its n-th iterated line graph for n≥1 or 2,3,and that every other connected graph thatembeds in its n-th iterated line graph may be constructed from such an embedded unicycle or tree ina natural way A special kind of embedding of graph into its n-th iterated line graph,called incidenceembedding,is studied.Moreover,it is shown that for every positive integer k,there exists a graph Gsuch that (?)(G)=k,where (?)(G) is the least n≥1 for which G embeds in L~n(G).     

On Sullivan��s conjecture on cycles in 4-free and 5-free digraphs

For a simple digraph G, let β(G) be the size of the smallest subset X■E(G) such that G-X has no directed cycles, and let γ(G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This paper proves that β(G) ≤ 0.3819γ(G) if G is a 4-free digraph, and β(G) ≤ 0.2679γ(G) if G is a 5-free digraph. These improve the results of Sullivan in 2008.     

三边连通超欧拉图的一个注记

For two integers l 0 and k ≥ 0,define C(l,k) to be the family of 2-edge connected graphs such that a graph G ∈ C(l,k) if and only if for every bond S-E(G) with |S| ≤ 3,each component of G-S has order at least(|V(G)|-k)/l.In this note we prove that if a 3-edge-connected simple graph G is in C(10,3),then G is supereulerian if and only if G cannot be contracted to the Petersen graph.Our result extends an earlier result in [Supereulerian graphs and Petersen graph.JCMCC 1991,9:79-89] by Chen.     

Characterization of L2(16) by Τe(L2(16))

Let G be a group and πe(G) the set of element orders of G.Let k∈πe(G) and m k be the number of elements of order k in G.Letτe(G)={mk|k∈πe(G)}.In this paper,we prove that L2(16) is recognizable byτe (L2(16)).In other words,we prove that if G is a group such that τe(G)=τe(L2(16))={1,255,272,544,1088,1920},then G is isomorphic to L2(16).     

用$\tau_e(L_2(16))$刻画$L_2(16)$

Let G be a group and πe(G) the set of element orders of G.Let k∈πe(G) and m k be the number of elements of order k in G.Letτe(G)={mk|k∈πe(G)}.In this paper,we prove that L2(16) is recognizable byτe (L2(16)).In other words,we prove that if G is a group such that τe(G)=τe(L2(16))={1,255,272,544,1088,1920},then G is isomorphic to L2(16).     

The densities for 3-ranks of tame kernels of cyclic cubic number fields

Let F be a cubic cyclic field with t(2)ramified primes.For a finite abelian group G,let r3(G)be the 3-rank of G.If 3 does not ramify in F,then it is proved that t-1 r3(K2O F)2t.Furthermore,if t is fixed,for any s satisfying t-1 s 2t-1,there is always a cubic cyclic field F with exactly t ramified primes such that r3(K2O F)=s.It is also proved that the densities for 3-ranks of tame kernels of cyclic cubic number fields satisfy a Cohen-Lenstra type formula d∞,r=3-r2∞k=1(1-3-k)r k=1(1-3-k)2.This suggests that the Cohen-Lenstra conjecture for ideal class groups can be extended to the tame kernels of cyclic cubic number fields.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

The Rainbow Vertex-disconnection in Graphs

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.     

Upper Bounds on List Star Chromatic Index of Sparse Graphs

A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_st(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(G)is defined analogously.The star edge coloring problem is known to be NP-complete,and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear.In this paper,we study,in contrast,the best linear upper bound for sparse graph classes.We show that for everyε>0 there exists a constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes.