Comparing motives of smooth algebraic varieties

Given a perfect field of exponential characteristic e, the Cor-, $K_0^{\oplus }$-, $K_0$- and ${\mathbb{K}}_0$-motives of smooth algebraic varieties with $\mathbb{Z}[1/e]$-coefficients are shown to be locally quasi-isomorphic to each other. Moreover, it is proved that their triangulated categories of motives with $\mathbb{Z}[1/e]$-coefficients are equivalent. An application is given for the bivariant motivic spectral sequence.     

Optimal spanners for axis-aligned rectangles

The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the $L_1$-distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their $L_1$-distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles.We study the following problem: given n non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i) for arbitrary graphs, the problem is NP-hard; (ii) for trees, we can solve the problem by linear programming on $\mathrm{O}(n^2)$ variables and constraints; (iii) for paths, we can solve the problem in time $\mathrm{O}(n^3\log n)$; (iv) for rectangles sorted vertically along a path, the problem can be solved in $\mathrm{O}(n^2)$ time, and a $(1+\varepsilon )$-approximation can be computed in linear time.     

Gap vertex-distinguishing edge colorings of graphs

In this paper, we study a new coloring parameter of graphs called the gap vertex-distinguishing edge coloring. It consists in an edge-coloring of a graph $G$ which induces a vertex distinguishing labeling of $G$ such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. The minimum number of colors required for a gap vertex-distinguishing edge coloring of $G$ is called the gap chromatic number of $G$ and is denoted by $\mathrm{gap}\left(G\right)$.We here study the gap chromatic number for a large set of graphs $G$ of order $n$ and prove that $\mathrm{gap}\left(G\right)\in \{n?1,n,n+1\}$.     

Star saturation number of random graphs

For a given graph $F$, the $F$-saturation number of a graph $G$ is the minimum number of edges in an edge-maximal $F$-free subgraph of $G$. Recently, the $F$-saturation number of the Erd?s–Rényi random graph $\mathbb{G}(n,p)$ has been determined asymptotically for any complete graph $F$. In this paper, we give an asymptotic formula for the $F$-saturation number of $\mathbb{G}(n,p)$ when $F$ is a star graph.     

Intersection Dimension and Maximum Degree

We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree Δ is at most $O(\mathrm{\Delta }\frac{\log \mathrm{\Delta }}{\log \log \mathrm{\Delta })}$. We also obtain bounds in terms of treewidth.     

Hamiltonicity of edge chromatic critical graphs

Vizing conjectured that every edge chromatic critical graph contains a 2-factor. Believing that stronger properties hold for this class of graphs, Luo and Zhao (2013) showed that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{6n}{7}$ is Hamiltonian. Furthermore, Luo et al. (2016) proved that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{4n}{5}$ is Hamiltonian. In this paper, we prove that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{3n}{4}$ is Hamiltonian. Our approach is inspired by the recent development of Kierstead path and Tashkinov tree techniques for multigraphs.