Gallai’s path decomposition conjecture for triangle-free planar graphs

A path decomposition of a graph $G$ is a collection of edge-disjoint paths of $G$ that covers the edge set of $G$. Gallai (1968) conjectured that every connected graph on $n$ vertices admits a path decomposition of cardinality at most $?(n+1)∕2?$. Gallai’s Conjecture has been verified for many classes of graphs. In particular, Lovász (1968) verified this conjecture for graphs with at most one vertex with even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex with odd degree. Recently, Bonamy and Perrett (2016) verified Gallai’s Conjecture for graphs with maximum degree at most 5, and Botler et al. (2017) verified it for graphs with treewidth at most 3. In this paper, we verify Gallai’s Conjecture for triangle-free planar graphs.     

A note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.     

Computing upward topological book embeddings of upward planar digraphs

We describe a unified approach for studying book, point-set, and simultaneous embeddability problems of upward planar digraphs. The approach is based on a linear time strategy to compute an upward planar drawing of an upward planar digraph such that all vertices are collinear. Besides having impact in relevant application domains of graph drawing and computational geometry, the presented results open new research directions in the area of upward planarity with constraints of the positions of the vertices.     

Universal point sets for planar three-trees

For every $n\in \mathbb{N}$, we present a set $S_n$ of $O(n^{3/2}\log n)$ points in the plane such that every planar 3-tree with n vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of $S_n$. This is the first subquadratic upper bound on the cardinality of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs.     

混合幂的素变数丢番图逼近

证明了,如果λ1,λ2,λ3,λ4是正实数,λ1/λ2是无理数和代数效,V是well-spaced序列,δ>0,那么对于ν,∈V,ν≤X,ε>0,使得|λ1p21+λ2p22+λ3p33+λ4p34-ν|<ν-δ没有素数解P1,p2,p3,p4的ν的个数不超过O(X20/21+2δ+ε).     

A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary odd girth

A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We provide a construction of an infinite family of polygonal graphs of arbitrary odd girth with 2-arc transitive automorphism groups.     

A graph-theoretic approach to a partial order of knots and links

We say that a link L₁ is an s-major of a link L₂ if any diagram of L₁ can be transformed into a diagram of L₂ by changing some crossings and smoothing some crossings. This relation is a partial ordering on the set of all prime alternating links. We determine this partial order for all prime alternating knots and links with the crossing number less than or equal to six. The proofs are given by graph-theoretic methods.     

Covering homology

We introduce the notion of covering homology of a commutative S-algebra with respect to certain families of coverings of topological spaces. The construction of covering homology is extracted from Bökstedt, Hsiang and Madsen's topological cyclic homology. In fact covering homology with respect to the family of orientation preserving isogenies of the circle is equal to topological cyclic homology. Our basic tool for the analysis of covering homology is a cofibration sequence involving homotopy orbits and a restriction map similar to the restriction map used in Bökstedt, Hsiang and Madsen's construction of topological cyclic homology.Covering homology with respect to families of isogenies of a torus is constructed from iterated topological Hochschild homology. It receives a trace map from iterated algebraic K-theory and there is a hope that the rich structure, and the calculability of covering homology will make it useful in the exploration of J. Rognes' “red shift conjecture”.