Circular vertex arboricity

The vertex arboricity va(G) of graph G is defined as the minimum of subsets in a partition of the vertex set of G so that each subset induces an acyclic subgraph and has been widely studied. We define the concept of circular vertex arboricity va_c(G) of graph G, which is a natural generalization of vertex arboricity. We give some basic properties of circular vertex arboricity and study the circular vertex arboricity of planar graphs.     

The linear arboricity of graphs

Alinear forest is a forest in which each connected component is a path. Thelinear arboricity la(G) of a graphG is the minimum number of linear forests whose union is the set of all edges ofG. Thelinear arboricity conjecture asserts that for every simple graphG with maximum degree Δ=Δ(G), . Although this conjecture received a considerable amount of attention, it has been proved only for Δ≦6, Δ=8 and Δ=10, and the best known general upper bound for la(G) is la(G)≦⌈3Δ/5⌉ for even Δ and la(G)≦⌈(3Δ+2)/5⌉ for odd Δ. Here we prove that for everyɛ>0 there is a Δ₀=Δ₀(ɛ) so that la(G)≦(1/2+ɛ)Δ for everyG with maximum degree Δ≧Δ₀. To do this, we first prove the conjecture for everyG with an even maximum degree Δ and withgirth g≧50Δ. Research supported in part by Allon Fellowship, by a Bat Sheva de Rothschild grant, by the Fund for Basic Research administered by the Israel Academy of Sciences and by a B.S.F. Bergmann Memorial grant.     

On the critical point‐arboricity graphs

In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of k‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph G embedded on a surface S with Euler genus g = 2, 5, 6 or g ≥ 10 is at most with equality holding iff G contains either K_2k?1 or K_2k?4 + C₅ as a subgraph. It is also proved that locally planar graphs have point‐arboricity ≤ 3 and that triangle‐free locally planar‐graphs have point‐arboricity ≤ 2. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 50–61, 2002     

On the linear arboricity of planar graphs

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ. The conjecture has been proved to be true for graphs having Δ = 1, 2, 3, 4, 5, 6, 8, 10. Combining these results, we prove in the article that the conjecture is true for planar graphs having Δ(G) ≠ 7. Several related results assuming some conditions on the girth are obtained as well. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 129–134, 1999     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

The vertex linear arboricity of distance graphs

A distance graph is a graph G(R,D) with the set of all points of the real line as vertex set and two vertices u,v∈R are adjacent if and only if |u-v|∈D where the distance set D is a subset of the positive real numbers. Here, the vertex linear arboricity of G(R,D) is determined when D is an interval between 1 and δ. In particular, the vertex linear arboricity of integer distance graphs G(D) is discussed, too.     

Star arboricity

Astar forest is a forest all of whose components are stars. Thestar arboricity, st(G) of a graphG is the minimum number of star forests whose union covers all the edges ofG. Thearboricity, A(G), of a graphG is the minimum number of forests whose union covers all the edges ofG. Clearlyst(G)A(G). In fact, Algor and Alon have given examples which show that in some casesst(G) can be as large asA(G)+(log) (where is the maximum degree of a vertex inG). We show that for any graphG, st(G)A(G)+O(log).     

Bounds for the vertex linear arboricity

The vertex linear arboricity vla(G) of a nonempty graph G is the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces a subgraph whose connected components are paths. This paper provides an upper bound for vla(G) of a connected nonempty graph G, namely vla(G) ≦ 1 + ?δ(G)/2? where δ(G) denotes the maximum degree of G. Moreover, if δ(G) is even, then vla(G) = 1 + ?δ(G)/2? if and only if G is either a cycle or a complete graph.     

Linear arboricity for graphs with multiple edges

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ(G), the linear arboricity la(G) satisfies ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + 1)/2?. Here it is proved that if G is a loopless graph with maximum degree Δ(G) ≦ k and maximum edge multiplicity μ(G) ≦ k ? 2ⁿ⁺¹ + 1, where k ≧ 2^n?2, then la(G) ≦ k ? 2ⁿ. It is also conjectured that for any loopless graph G, ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + μ(G))/2?.     

Some results on linear arboricity

The linear arboricity of the graph G is the minimum number of linear forests whose union is G. In the paper exact values and bounds of linear arboricity for some additional classes of graphs are determined.     

The game of arboricity

Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by A_g(G). We prove that A_g(G)?3k for any graph G of arboricity k, and that there are graphs such that A_g(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.     

List Point Arboricity of Dense Graphs

Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ _l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ _l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ _l (G + K _n ) = ρ(G + K _n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ _l (G) = ρ(G). Particularly, we determine that , where K _2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ _l (G) = ρ(G). Research supported by NSFC (No.10601044) and XJEDU2006S05.     

A note on the list vertex arboricity of toroidal graphs

The vertex arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of colors required to color the vertices of $G$ such that no cycle is monochromatic. The list vertex arboricity $a_l\left(G\right)$ is the list-coloring version of this concept. In this note, we prove that if $G$ is a toroidal graph, then $a_l\left(G\right)\le 4$; and $a_l\left(G\right)=4$ if and only if $G$ contains $K_7$ as an induced subgraph.     

Caterpillar arboricity of planar graphs

We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469-478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph G=(V,E), the edge set E can be partitioned into four subsets (E_i)_1?i?4 in such a way that G[E_i], for 1?i?4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G.     

Undirected power graphs of semigroups

The undirected power graph G(S) of a semigroup S is an undirected graph whose vertex set is S and two vertices a,b∈S are adjacent if and only if a≠b and a ^m =b or b ^m =a for some positive integer m. In this paper we characterize the class of semigroups S for which G(S) is connected or complete. As a consequence we prove that G(G) is connected for any finite group G and G(G) is complete if and only if G is a cyclic group of order 1 or p ^m . Particular attention is given to the multiplicative semigroup ℤ _n and its subgroup U _n , where G(U _n ) is a major component of G(ℤ _n ). It is proved that G(U _n ) is complete if and only if n=1,2,4,p or 2p, where p is a Fermat prime. In general, we compute the number of edges of G(G) for a finite group G and apply this result to determine the values of n for which G(U _n ) is planar. Finally we show that for any cyclic group of order greater than or equal to 3, G(G) is Hamiltonian and list some values of n for which G(U _n ) has no Hamiltonian cycle.     

On Groups with Frobenius Elements

It is proved that group G contains an Abelian normal periodic complement to C_G(a²) if a is an H-Frobenius element a of order 4 of G. Mathematics Subject Classification (2000) 20E25.     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

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     

The Linear Arboricity of Series-Parallel Graphs

 The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. A graph is called series-parallel if it contains no subgraphs homeomorphic to K ₄. In this paper, we prove that for any series-parallel graph G having Δ (G)≥3. Since an outerplanar graph is a series-parallel graph, this is also true for any outerplanar graph. Received: August 20, 1997 Revised: March 12, 1999     

Decomposition of bipartite graphs into closed trails

Let Lct(G) denote the set of all lengths of closed trails that exist in an even graph G. A sequence (t ₁,..., t _p ) of elements of Lct(G) adding up to |E(G)| is G-realisable provided there is a sequence (T ₁,..., t _p ) of pairwise edge-disjoint closed trails in G such that T _i is of length T _i for i = 1,..., p. The graph G is arbitrarily decomposable into closed trails if all possible sequences are G-realisable. In the paper it is proved that if a ⩾ 1 is an odd integer and M _a,a is a perfect matching in K _a,a , then the graph K _a,a -M _a,a is arbitrarily decomposable into closed trails.      

An inequality for Tutte polynomials

Let G be a graph without loops or bridges and a, b be positive real numbers with b ≥ a(a+2). We show that the Tutte polynomial of G satisfies the inequality T _G (b, 0)T _G (0, b) ≥ T _G (a, a)². Our result was inspired by a conjecture of Merino and Welsh that T _G (1, 1) ≤ max{T _G (2, 0),T _G (0, 2)}.