On planar hypohamiltonian graphs

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for every integer n≥N there exists a planar hypohamiltonian/hypotraceable graph on n vertices. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 55‐68, 2011     

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     

Realizing finite edge‐transitive orientable maps

J.E. Graver and M.E. Watkins, Memoirs Am. Math. Soc. 126 (601) ( 5 ) established that the automorphism group of an edge‐transitive, locally finite map manifests one of exactly 14 algebraically consistent combinations (called types) of the kinds of stabilizers of its edges, its vertices, its faces, and its Petrie walks. Exactly eight of these types are realized by infinite, locally finite maps in the plane. H.S.M. Coxeter (Regular Polytopes, 2nd ed., McMillan, New York, 1963) had previously observed that the nine finite edge‐transitive planar maps realize three of the eight planar types. In the present work, we show that for each of the 14 types and each integer n ≥ 11 such that n ≡ 3,11 (mod 12), there exist finite, orientable, edge‐transitive maps whose various stabilizers conform to the given type and whose automorphism groups are (abstractly) isomorphic to the symmetric group Sym(n). Exactly seven of these types (not a subset of the planar eight) are shown to admit infinite families of finite, edge‐transitive maps on the torus, and their automorphism groups are determined explicitly. Thus all finite, edge‐transitive toroidal maps are classified according to this schema. Finally, it is shown that exactly one of the 14 types can be realized as an abelian group of an edge‐transitive map, namely, as ?_n × ?₂ where n ≡ 2 (mod 4). © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 1–34, 2001     

Coloring the square of a planar graph

We prove that for any planar graph G with maximum degree Δ, it holds that the chromatic number of the square of G satisfies χ(G²) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 110–124, 2003     

Simplicial Properties of the Set of Planar Binary Trees

Planar binary trees appear as the the main ingredient of a new homology theory related to dialgebras, cf.(J.-L. Loday, C.R. Acad. Sci. Paris 321 (1995), 141–146.) Here I investigate the simplicial properties of the set of these trees, which are independent of the dialgebra context though they are reflected in the dialgebra homology.The set of planar binary trees is endowed with a natural (almost) simplicial structure which gives rise to a chain complex. The main new idea consists in decomposing the set of trees into classes, by exploiting the orientation of their leaves. (This trick has subsequently found an application in quantum electrodynamics, c.f. (C. Brouder, On the Trees of Quantum Fields, Eur. Phys. J. C12, 535–549 (2000).) This decomposition yields a chain bicomplex whose total chain complex is that of binary trees. The main theorem of the paper concerns a further decomposition of this bicomplex. Each vertical complex is the direct sum of subcomplexes which are in bijection with the planar binary trees. This decomposition is used in the computation of dialgebra homology as a derived functor, cf. (A. Frabetti, Dialgebra (co) Homology with Coefficients, Springer L.N.M., to appear).     

Infinitely many planar cubic hypohamiltonian graphs of girth 5

A graph G is hypohamiltonian if G is non‐hamiltonian and for every vertex v in G, the graph is hamiltonian. McKay asked in [J. Graph Theory 85 (2017) 7–11] whether infinitely many planar cubic hypohamiltonian graphs of girth 5 exist. We settle this question affirmatively.     

Tannakian duality for Anderson–Drinfeld motives and algebraic independence of Carlitz logarithms

We develop a theory of Tannakian Galois groups for t-motives and relate this to the theory of Frobenius semilinear difference equations. We show that the transcendence degree of the period matrix associated to a given t-motive is equal to the dimension of its Galois group. Using this result we prove that Carlitz logarithms of algebraic functions that are linearly independent over the rational function field are algebraically independent. Mathematics Subject Classification (2000) Primary: 11J93; Secondary: 11G09, 12H10, 14L17     

Complex planar splines

In contradistinction to the known theory on complex splines which are defined on the boundary of a region in , we define complex planar splines on a region itself as a complex valued continuous function which is defined piecewise on suitable meshes of that region. The main idea is to use nonholomorphic functions as pieces, since holomorphic pieces would lead to just one holomorphic function on the whole region. Some of the techniques used are available from the theory of finite elements. But we also consider new aspects, namely, mapping properties of a complex planar spline v and the difference f − v, where f is, in general, a holomorphic function. For triangular meshes, rectangular and parallelogrammatic meshes, and meshes on circular sectors, explicit expressions are provided; also properties of the newly introduced complex planar splines are studied.     

N-distance tests for a composite hypothesis of goodness of fit

In this paper, we consider an application of N-distance theory for testing composite hypotheses of goodness of fit. This work is a continuation of our research started in [A. Bakshaev, Goodness of fit and homogeneity tests on the basis of N-distances, J. Stat. Plan. Inference, 139(11):3750–3758, 2009; A. Bakshaev, Nonparametric tests based on N-distances, Lith. Math. J., 48(4):368–379, 2008]. Particular attention is paid to normality and exponentiality tests. A comparative Monte Carlo power study for the proposed criteria is provided. Different alternatives in uni- and bivariate cases are investigated.     

Infinite paths in planar graphs II,structures and ladder nets

A graph is k‐indivisible, where k is a positive integer, if the deletion of any finite set of vertices results in at most k – 1 infinite components. In 1971, Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if and only if it is 3‐indivisible. In this paper, we prove a structural result for 2‐indivisible infinite planar graphs. This structural result is then used to prove Nash‐Williams conjecture for all 4‐connected 2‐indivisible infinite planar graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 247–266, 2005     

Star coloring bipartite planar graphs

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eight colors to star color. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 1–10, 2009     

Acyclic 5‐choosability of planar graphs without adjacent short cycles

The conjecture on acyclic 5‐choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4‐cycles. We prove that a planar graph is acyclically 5‐choosable if it does not contain an i‐cycle adjacent to a j‐cycle where 3?j?5 if i = 3 and 4?j?6 if i = 4. This result absorbs most of the previous work in this direction. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:169‐176, 2011     

No optimal 1‐planar graph triangulates any nonorientable closed surface

Suzuki [Discrete Math. 310 (2010), 6–11] proved that for any orientable closed surface F² other than the sphere, there exists an optimal 1‐planar graph which can be embedded on F² as a triangulation. However, for nonorientable closed surfaces, the existence of such graphs is unknown. In this article, we prove that no optimal 1‐planar graph triangulates a nonorientable closed surface.     

Planar 3DM is NP-complete

A restriction of the three-dimensional matching problem 3DM, in which the associated bipartite graph is planar, is shown to remain NP-complete. The restriction is inspired by that of Lichtenstein's planar 3SAT (Planar formulae and their uses, SIAM J. Comput. 11 (1982), 329–343). Like Planar 3SAT, Planar 3DM is principally a tool for use in NP-completeness proofs for planar restrictions of other problems. Several examples of its applications in this respect are given.     

Antisymmetric flows on planar graphs

We prove that every oriented planar graph admits a homomorphism to the Paley tournament P₂₇₁ and hence that every oriented planar graph has an antisymmetric flow number and a strong oriented chromatic number of at most 271. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 200–210, 2006     

K4,4 − e has no finite planar cover

A graph G has a planar cover if there exists a planar graph H , and a homomorphism φ : H → G that maps the neighbors of each vertex bijectively. Each graph that has an embedding in the projective plane also has a finite planar cover. Negami conjectured the converse in 1988. This conjecture holds as long as no minor-minimal nonprojective graph has a finite planar cover. From the list there remain only two cases not solved yet—the graphs K _4,4 − e and K _1,2,2,2. We prove the nonexistence of a finite planar cover of K _4,4 − e. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 51–60, 1998     

The stability of linear periodic Hamiltonian systems on time scales

In this work, we give a new stability criterion for planar periodic Hamiltonian systems, improving the results from the literature. The method is based on an application of the Floquet theory recently established in [J.J. DaCunha, J.M. Davis, A unified Floquet theory for discrete, continuous, and hybrid periodic linear systems, J. Differential Equations 251 (2011) 2987–3027], and the use of a new definition for a generalized zero. The results obtained not only unify the related continuous and discrete ones but also provide sharper stability criteria for the discrete case.     

Counting 5‐connected planar triangulations

Let t_n be the number of rooted 5‐connected planar triangulations with 2n faces. We find t_n exactly for small n, as well as an asymptotic formula for n → ∞. Our results are found by compositions of lower connectivity maps whose faces are triangles or quadrangles. We also find the asymptotic number of cyclically 5‐edge connected cubic planar graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 18–35, 2001     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

Star coloring planar graphs from small lists

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324–337, 2010