Claw‐decompositions and tutte‐orientations

We conjecture that, for each tree T, there exists a natural number k_T such that the following holds: If G is a k_T‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K_1,3 (the claw), this holds if and only if there exists a (smallest) natural number k_t such that every k_t‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that k_t = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006     

The Crank‐Nicolson/Adams‐Bashforth scheme for the time‐dependent Navier‐Stokes equations with nonsmooth initial data

In this article, we study the stability and convergence of the Crank‐Nicolson/Adams‐Bashforth scheme for the two‐dimensional nonstationary Navier‐Stokes equations with a nonsmooth initial data. A finite element method is applied for the spatial approximation of the velocity and pressure. The time discretization is based on the implicit Crank‐Nicolson scheme for the linear terms and the explicit Adams‐Bashforth scheme for the nonlinear term. Moreover, we prove that the scheme is almost unconditionally stable for a nonsmooth initial data u₀ with div u₀ = 0, i.e., the time step τ satisfies: τ ≤ C₀ if u₀ ∈ H¹ ∩ L^∞; τ |log h| ≤ C₀ if u₀ ∈ H¹ for the mesh size h and some positive constant C₀. Finally, we obtain some error estimates for the discrete velocity and pressure under the above stability condition. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 28: 155‐187, 2012     

Blow‐up for the b‐family of equations

In this paper, we consider the b‐family of equations on the torus u _t ?u _{t x x} +(b + 1)u u _x =b u _x u _{x x} +u u _{x x x} , which for appropriate values of b reduces to well‐known models, such as the Camassa–Holm equation or the Degasperis–Procesi equation. We establish a local‐in‐space blow‐up criterion. Copyright © 2016 John Wiley & Sons, Ltd.     

d‐homogeneous and d‐ultrahomogeneous linear spaces

A linear space S is d‐homogeneous if, whenever the linear structures induced on two subsets S₁ and S₂ of cardinality at most d are isomorphic, there is at least one automorphism of S mapping S₁ onto S₂. S is called d‐ultrahomogeneous if each isomorphism between the linear structures induced on two subsets of cardinality at most d can be extended into an automorphism of S. We have proved in [11;] (without any finiteness assumption) that every 6‐homogeneous linear space is homogeneous (that is d‐homogeneous for every positive integer d). Here we classify completely the finite nontrivial linear spaces that are d‐homogeneous for d ≥ 4 or d‐ultrahomogeneous for d ≥ 3. We also prove an existence theorem for infinite nontrivial 4‐ultrahomogeneous linear spaces. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 321–329, 2000     

Facial non‐repetitive edge‐coloring of plane graphs

A sequence r₁, r₂, …, r_2n such that r_i=r_{n+ i} for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′_f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′_f(G)≤8 for any plane graph G. We also get better upper bounds for π′_f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010     

Claw‐free 3‐connected P11‐free graphs are hamiltonian

We show that every 3‐connected claw‐free graph which contains no induced copy of P₁₁ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of P₁₂ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Time‐weighted blow‐up rates and pointwise profile for single‐point blow‐up solutions in reaction–diffusion equations

This paper deals with asymptotic behavior for blow‐up solutions to time‐weighted reaction–diffusion equations u_t=Δu+e^αtv^p and v_t=Δv+e^βtu^q, subject to homogeneous Dirichlet boundary. The time‐weighted blow‐up rates are defined and obtained by ways of the scaling or auxiliary‐function methods for all α, . Aiding by key inequalities between components of solutions, we give lower pointwise blow‐up profiles for single‐point blow‐up solutions. We also study the solutions of the system with variable exponents instead of constant ones, where blow‐up rates and new blow‐up versus global existence criteria are obtained. Time‐weighted functions influence critical Fujita exponent, critical Fujita coefficient and formulae of blow‐up rates, but they do not limit the order of time‐weighted blow‐up rates and pointwise profile near blow‐up time. Copyright © 2017 John Wiley & Sons, Ltd.     

Y‐rotation in k‐minimal quadrangulations on the projective plane

Let G be a quadrangulation on a surface, and let f be a face bounded by a 4‐cycle abcd. A face‐contraction of f is to identify a and c (or b and d) to eliminate f. We say that a simple quadrangulation G on the surface is k‐minimal if the length of a shortest essential cycle is k(≥3), but any face‐contraction in G breaks this property or the simplicity of the graph. In this article, we shall prove that for any fixed integer k≥3, any two k‐minimal quadrangulations on the projective plane can be transformed into each other by a sequence of Y‐rotations of vertices of degree 3, where a Y‐rotation of a vertex v of degree 3 is to remove three edges vv₁, vv₃, vv₅ in the hexagonal region consisting of three quadrilateral faces vv₁v₂v₃, vv₃v₄v₅, and vv₅v₆v₁, and to add three edges vv₂, vv₄, vv₆. Actually, every k‐minimal quadrangulation (k≥4) can be reduced to a (k?1)‐minimal quadrangulation by the operation called Möbius contraction, which is mentioned in Lemma 13. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 301–313, 2012     

Monochromatic Hamiltonian t‐tight Berge‐cycles in hypergraphs

In any r‐uniform hypergraph for 2 ≤ t ≤ r we define an r‐uniform t‐tight Berge‐cycle of length ?, denoted by C_?^{(r, t)}, as a sequence of distinct vertices v₁, v₂, … , v_?, such that for each set (v_i, v_{i + 1}, … , v_{i + t ? 1}) of t consecutive vertices on the cycle, there is an edge E_i of that contains these t vertices and the edges E_i are all distinct for i, 1 ≤ i ≤ ?, where ? + j ≡ j. For t = 2 we get the classical Berge‐cycle and for t = r we get the so‐called tight cycle. In this note we formulate the following conjecture. For any fixed 2 ≤ c, t ≤ r satisfying c + t ≤ r + 1 and sufficiently large n, if we color the edges of K_n^(r), the complete r‐uniform hypergraph on n vertices, with c colors, then there is a monochromatic Hamiltonian t‐tight Berge‐cycle. We prove some partial results about this conjecture and we show that if true the conjecture is best possible. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 34–44, 2008     

The existence of a 2‐factor in K1, n‐free graphs with large connectivity and large edge‐connectivity

In this article, we study the existence of a 2‐factor in a K_{1, n}‐free graph. Sumner [J London Math Soc 13 (1976), 351–359] proved that for n?4, an (n?1)‐connected K_{1, n}‐free graph of even order has a 1‐factor. On the other hand, for every pair of integers m and n with m?n?4, there exist infinitely many (n?2)‐connected K_{1, n}‐free graphs of even order and minimum degree at least m which have no 1‐factor. This implies that the connectivity condition of Sumner's result is sharp, and we cannot guarantee the existence of a 1‐factor by imposing a large minimum degree. On the other hand, Ota and Tokuda [J Graph Theory 22 (1996), 59–64] proved that for n?3, every K_{1, n}‐free graph of minimum degree at least 2n?2 has a 2‐factor, regardless of its connectivity. They also gave examples showing that their minimum degree condition is sharp. But all of them have bridges. These suggest that the effects of connectivity, edge‐connectivity and minimum degree to the existence of a 2‐factor in a K_{1, n}‐free graph are more complicated than those to the existence of a 1‐factor. In this article, we clarify these effects by giving sharp minimum degree conditions for a K_{1, n}‐free graph with a given connectivity or edge‐connectivity to have a 2‐factor. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 68:77‐89, 2011     

Defective choosability of graphs with no edge‐plus‐independent‐set minor

It is proved that, if s ≥ 2, a graph that does not have K₂ + K _s = K₁ + K_{1, s} as a minor is (s, 1)*‐choosable. This completes the proof that such a graph is (s + 1 ? d,d)*‐choosable whenever 0 ≤ d ≤ s ?1 © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 51–56, 2004     

Hamiltonian N2‐locally connected claw‐free graphs

A graph G is N₂‐locally connected if for every vertex ν in G, the edges not incident with ν but having at least one end adjacent to ν in G induce a connected graph. In 1990, Ryjá?ek conjectured that every 3‐connected N₂‐locally connected claw‐free graph is Hamiltonian. This conjecture is proved in this note. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 142–146, 2005     

On the Hamilton‐Waterloo Problem for Bipartite 2‐Factors

Given two 2‐regular graphs F₁ and F₂, both of order n, the Hamilton‐Waterloo Problem for F₁ and F₂ asks for a factorization of the complete graph into α₁ copies of F₁, α₂ copies of F₂, and a 1‐factor if n is even, for all nonnegative integers α₁ and α₂ satisfying . We settle the Hamilton‐Waterloo Problem for all bipartite 2‐regular graphs F₁ and F₂ where F₁ can be obtained from F₂ by replacing each cycle with a bipartite 2‐regular graph of the same order.     

4‐Coloring P6‐Free Graphs with No Induced 5‐Cycles

We show that the 4‐coloring problem can be solved in polynomial time for graphs with no induced 5‐cycle C₅ and no induced 6‐vertex path P₆     

Groups and C*‐Algebras from a 4‐Dimensional Anzai Flow

The rotation flow on the circle T gives a concrete representation of the irrational rotation algebra, which is an in finite dimensional simple quotient of the group C*‐algebra of the discrete Heisenberg group H₃ analogously certain 2‐ and 3‐dimensional Anzai flows on T ² and T ³are known to give concrete representations of the corresponding quotients of the group C*‐algebras of the groups H₄ and H_5,5. Considered here is the (minimal, effective) 4‐dimensional Anzai flow F = (ℤ, T ⁴) generated by the homeomorphism (y, x, w, v) ↦ (λy, yx, xw, wv); a group H_6,10 is determined by F the faithful in finite dimensional simple quotients of whose group C*‐algebra C*‐(H_6,10 have concrete representations given by F. Furthermore, the rest of the infinite dimensional simple quotients of C*‐(H_6,10 are identified and displayed as C*‐crossed products generated by minimal effective actions and also as matrix algebras over simple C*‐algebras from groups of lower dimension; these lower dimensional groups are H₃ and subgroups of H₄ and H_5,5.     

A note on the first‐order logic of complete BL‐chains

In [10] it is claimed that the set of predicate tautologies of all complete BL‐chains and the set of all standard tautologies (i. e., the set of predicate formulas valid in all standard BL‐algebras) coincide. As noticed in [11], this claim is wrong. In this paper we show that a complete BL‐chain B satisfies all standard BL‐tautologies iff for any transfinite sequence (a_i: i ∈ I) of elements of B , the condition ∧_{i ∈ I} (a²_i ) = (∧_{i ∈ I} a_i)² holds in B . (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

Anti‐Ramsey numbers of doubly edge‐critical graphs

Given a graph H and a positive integer n, Anti‐Ramsey number AR(n, H) is the maximum number of colors in an edge‐coloring of K_n that contains no polychromatic copy of H. The anti‐Ramsey numbers were introduced in the 1970s by Erd?s, Simonovits, and Sós, who among other things, determined this function for cliques. In general, few exact values of AR(n, H) are known. Let us call a graph H doubly edge‐critical if χ(H?e)≥p+ 1 for each edge e∈E(H) and there exist two edges e₁, e₂ of H for which χ(H?e₁?e₂)=p. Here, we obtain the exact value of AR(n, H) for any doubly edge‐critical H when n?n₀(H) is sufficiently large. A main ingredient of our proof is the stability theorem of Erd?s and Simonovits for the Turán problem. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 210–218, 2009