Note on the path‐matching formula

As a common generalization of matchings and matroid intersections, W.H. Cunningham and J.F. Geelen introduced the notion of path‐matchings. They proved a min‐max formula for the maximum value. Here, we exhibit a simplified version of their min‐max theorem and provide a purely combinatorial proof. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 110–119, 2002     

On many‐sorted algebraic closure operators

A theorem of Birkhoff‐Frink asserts that every algebraic closure operator on an ordinary set arises, from some algebraic structure on the set, as the corresponding generated subalgebra operator. However, for many‐sorted sets, i.e., indexed families of sets, such a theorem is not longer true without qualification. We characterize the corresponding many‐sorted closure operators as precisely the uniform algebraic operators. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Even‐hole‐free graphs part I: Decomposition theorem

We prove a decomposition theorem for even‐hole‐free graphs. The decompositions used are 2‐joins and star, double‐star and triple‐star cutsets. This theorem is used in the second part of this paper to obtain a polytime recognition algorithm for even‐hole‐free graphs. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 6–49, 2002     

6‐Star‐Coloring of Subcubic Graphs

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2‐colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6‐star‐colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, and Reed (J Graph Theory 47(3) (2004), 140–153).     

Degree Conditions for Matchability in 3‐Partite Hypergraphs

We study conjectures relating degree conditions in 3‐partite hypergraphs to the matching number of the hypergraph, and use topological methods to prove special cases. In particular, we prove a strong version of a theorem of Drisko [14] (as generalized by the first two authors [2]), that every family of $2n-1$ matchings of size n in a bipartite graph has a partial rainbow matching of size n. We show that milder restrictions on the sizes of the matchings suffice. Another result that is strengthened is a theorem of Cameron and Wanless [11], that every $n\times n$ Latin square has a generalized diagonal (set of n entries, each in a different row and column) in which no symbol appears more than twice. We show that the same is true under the weaker condition that the square is row‐Latin.     

Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐Coloring

Chen et al., conjectured that for r≥3, the only connected graphs with maximum degree at most r that are not equitably r‐colorable are K_{r, r} (for odd r) and K_{r + 1}. If true, this would be a joint strengthening of the Hajnal–Szemerédi theorem and Brooks' theorem. Chen et al., proved that their conjecture holds for r = 3. In this article we study properties of the hypothetical minimum counter‐examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r≤4. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:31–48, 2012     

The algebra of set functions II: An enumerative analogue of Hall’s theorem for bipartite graphs

Triesch (1997) [25] conjectured that Hall’s classical theorem on matchings in bipartite graphs is a special case of a phenomenon of monotonicity for the number of matchings in such graphs. We prove this conjecture for all graphs with sufficiently many edges by deriving an explicit monotonic formula counting matchings in bipartite graphs.This formula follows from a general duality theory which we develop for counting matchings. Moreover, we make use of generating functions for set functions as introduced by Lass [20], and we show how they are useful for counting matchings in bipartite graphs in many different ways.     

On Finite 2‐Path‐Transitive Graphs

The class of graphs that are 2‐path‐transitive but not 2‐arc‐transitive is investigated. The amalgams for such graphs are determined, and structural information regarding the full automorphism groups is given. It is then proved that a graph is 2‐path‐transitive but not 2‐arc‐transitive if and only if its line graph is half‐arc‐transitive, thus providing a method for constructing new families of half‐arc‐transitive graphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 225–237, 2013     

Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles

Every planar graph is known to be acyclically 7‐choosable and is conjectured to be acyclically 5‐choosable (O. V. Borodin, D. G. Fon‐Der‐Flaass, A. V. Kostochka, E. Sopena, J Graph Theory 40 (2002), 83–90). This conjecture if proved would imply both Borodin's (Discrete Math 25 (1979), 211–236) acyclic 5‐color theorem and Thomassen's (J Combin Theory Ser B 62 (1994), 180–181) 5‐choosability theorem. However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4‐ and 3‐choosable. In particular, the acyclic 4‐choosability was proved for the following planar graphs: without 3‐, 4‐, and 5‐cycles (M. Montassier, P. Ochem, and A. Raspaud, J Graph Theory 51 (2006), 281–300), without 4‐, 5‐, and 6‐cycles, or without 4‐, 5‐, and 7‐cycles, or without 4‐, 5‐, and intersecting 3‐cycles (M. Montassier, A. Raspaud, W. Wang, Topics Discrete Math (2006), 473–491), and neither 4‐ and 5‐cycles nor 8‐cycles having a triangular chord (M. Chen and A. Raspaud, Discrete Math. 310(15–16) (2010), 2113–2118). The purpose of this paper is to strengthen these results by proving that each planar graph without 4‐ and 5‐cycles is acyclically 4‐choosable.     

Well‐posedness of the equations governing the motions of a one‐dimensional hybrid thermo‐elastic structure

In this paper a model for the vibrations of a one‐dimensional hybrid thermo‐elastic structure consisting of an extensible thermo‐elastic beam which is hinged at one end, with a rigid body attached to its free end, is studied with a view to establishing the existence of a unique solution in a weak sense. The model takes account of the effect of stretching on bending and rotational inertia. By treating eigenvalue problems with the spectral parameter also in the boundary conditions, we are able to employ the method of Faedo–Galerkin approximations. Copyright © 2004 John Wiley & Sons, Ltd.     

More About Geršgorin‐type theorems

In the recent book of R.S. Varga, [3], one of two main recurring themes is that a nonsingular theorem for matrices gives rise to an equivalent eigenvalue inclusion set in the complex plane, and conversely. If such nonsingularity result can be extended via irreducibility, usually this can be used for obtaining more information about the boundary of the corresponding eigenvalue inclusion set. Here we will start with one of Geršgorin‐type theorem for eigenvalue inclusion, given in [1], (for which exists corresponding equivalent statement about nonsingularity of a particular class of matrices) and use it for proving necessary conditions for an eigenvalue to lie on the boundary of localization area. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

High‐resolution monotone schemes based on quasi‐characteristics technique

In this article, we consider a new technique that allows us to overcome the well‐known restriction of Godunov's theorem. According to Godunov's theorem, a second‐order explicit monotone scheme does not exist. The techniques in the construction of high‐resolution schemes with monotone properties near the discontinuities of the solution lie in choosing of one of two high‐resolution numerical solutions computed on different stencils. The criterion for choosing the final solution is proposed. Results of numerical tests that compare with the exact solution and with the numerical solution obtained by the first‐order monotone scheme are presented. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 262–276, 2001     

3‐colorability of 4‐regular hamiltonian graphs

On the model of the cycle‐plus‐triangles theorem, we consider the problem of 3‐colorability of those 4‐regular hamiltonian graphs for which the components of the edge‐complement of a given hamiltonian cycle are non‐selfcrossing cycles of constant length ≥ 4. We show that this problem is NP‐complete. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 125–140, 2003     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Glivenko like theorems in natural expansions of BCK‐logic

The classical Glivenko theorem asserts that a propositional formula admits a classical proof if and only if its double negation admits an intuitionistic proof. By a natural expansion of the BCK‐logic with negation we understand an algebraizable logic whose language is an expansion of the language of BCK‐logic with negation by a family of connectives implicitly defined by equations and compatible with BCK‐congruences. Many of the logics in the current literature are natural expansions of BCK‐logic with negation. The validity of the analogous of Glivenko theorem in these logics is equivalent to the validity of a simple one‐variable formula in the language of BCK‐logic with negation. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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     

Global non‐existence of solutions of a class of wave equations with non‐linear damping and source terms

In this paper we consider the non‐linear wave equation a,b>0, associated with initial and Dirichlet boundary conditions. We prove, under suitable conditions on α,β,m,p and for negative initial energy, a global non‐existence theorem. This improves a result by Yang (Math. Meth. Appl. Sci. 2002; 25 :825–833), who requires that the initial energy be sufficiently negative and relates the global non‐existence of solutions to the size of Ω. Copyright © 2004 John Wiley & Sons, Ltd.     

Local existence of the solution to the initial‐boundary value problem in nonlinear thermomicroelasticity theory

We prove a theorem about local existence (in time) of the solution to the first initial‐boundary value problem for a nonlinear system of equation of the thermomicroelasticity theory. At first, we prove existence, uniqueness and regularity of the solution to this problem for the associated linearized system by using the method of semi‐group theory. Next, basing on this theorem, we prove an energy estimate for the solution to the linearized system by applying the method of Sobolev space. At the end, using the Banach fixed point theorem, we prove that the solution of our nonlinear problem exists and is unique. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fan‐type theorem for path‐connectivity

For a connected noncomplete graph G, let μ(G):=min{max {d_G(u), d_G(v)}:d_G(u, v)=2}. A well‐known theorem of Fan says that every 2‐connected noncomplete graph has a cycle of length at least min{|V(G)|, 2μ(G)}. In this paper, we prove the following Fan‐type theorem: if G is a 3‐connected noncomplete graph, then each pair of distinct vertices of G is joined by a path of length at least min{|V(G)|?1, 2μ(G)?2}. As consequences, we have: (i) if G is a 3‐connected noncomplete graph with , then G is Hamilton‐connected; (ii) if G is a (s+2)‐connected noncomplete graph, where s≥1 is an integer, then through each path of length s of G there passes a cycle of length≥min{|V(G)|, 2μ(G)?s}. Several results known before are generalized and a conjecture of Enomoto, Hirohata, and Ota is proved. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 265–282, 2002 DOI 10.1002/jgt.10028     

Applying geometric K‐cycles to fractional indices

A geometric model for twisted K‐homology is introduced. It is modeled after the Mathai–Melrose–Singer fractional analytic index theorem in the same way as the Baum–Douglas model of K‐homology was modeled after the Atiyah–Singer index theorem. A natural transformation from twisted geometric K‐homology to the new geometric model is constructed. The analytic assembly mapping to analytic twisted K‐homology in this model is an isomorphism for torsion twists on a finite ‐complex. For a general twist on a smooth manifold the analytic assembly mapping is a surjection. Beyond the aforementioned fractional invariants, we study T‐duality for geometric cycles.