The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

The minimum volume of subspace trades

A subspace bitrade of type $T_q(t,k,v)$ is a pair $(T_0,T_1)$ of two disjoint nonempty collections of $k$-dimensional subspaces of a $v$-dimensional space $V$ over the finite field of order $q$ such that every $t$-dimensional subspace of $V$ is covered by the same number of subspaces from $T_0$ and $T_1$. In a previous paper, the minimum cardinality of a subspace $T_q(t,t+1,v)$ bitrade was established. We generalize that result by showing that for admissible $v$, $t$, and $k$, the minimum cardinality of a subspace $T_q(t,k,v)$ bitrade does not depend on $k$. An example of a minimum bitrade is represented using generator matrices in the reduced echelon form. For $t=1$, the uniqueness of a minimum bitrade is proved.     

Injective choosability of subcubic planar graphs with girth 6

An injective coloring of a graph $G$ is an assignment of colors to the vertices of $G$ so that any two vertices with a common neighbor have distinct colors. A graph $G$ is injectively $k$-choosable if for any list assignment $L$, where $\left|L\left(v\right)\right|\ge k$ for all $v\in V\left(G\right)$, $G$ has an injective $L$-coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens the result of Lu?ar, ?krekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases.     

On 1-Sarvate–Beam designs

The solution to a set theory exercise, “Partition the set of positive integers $\{1,2,\dots ,v\}$ into $k$ subsets such that the sum of the elements in each subset is $v(v+1)/\left(2k\right)$ whenever $v(v+1)/\left(2k\right)$ is an integer”, gives a construction of non-simple 1-SB designs. This raises a natural question of the existence of simple 1-SB designs. We show that the necessary conditions for the existence of simple 1-SB designs for block sizes 2, 3, 4, 5 and 6 are sufficient. Moreover, the technique exhibited in the proof can be applied to block sizes greater than $k=6$. We also show that simple $t\text{-}\mathrm{SB}(v,t+1)$, $2\text{-}\mathrm{SB}(v,3)$ and $2\text{-}\mathrm{SB}(v,4)$ designs do not exist for any positive integers $v$ and $t$.A natural question, “Can we obtain a construction for simple 1-SB designs similar to Billington’s classical construction of simple 1-designs for any block size $k$?”, remains open.     

Blow-up for coupled nonlinear wave equations with damping and source

We consider the system of nonlinear wave equations $\{\begin{array}{cc}{u}_{tt}+u_t+{\left|u_t\right|}^{m?1}{u}_t=\mathrm{div}\left({\rho }_1\left({\left|?u\right|}^2\right)?u\right)+f_1(u,v)\text{,}\hfill & (x,t)\in \Omega \times (0,T)\text{,}\hfill \\ v_{tt}+v_t+{\left|v_t\right|}^{r?1}{v}_t=\mathrm{div}\left({\rho }_2\left({\left|?v\right|}^2\right)?v\right)+f_2(u,v)\text{,}\hfill & (x,t)\in \Omega \times (0,T)\text{,}\hfill \end{array}$ with initial and Dirichlet boundary conditions. Under some suitable assumptions on the functions$f_1$, $f_2$, ${\rho }_1$, ${\rho }_2$, parameters $r,m$ and the initial data, the result on blow-up of solutions and upper bound of blow-up time are given.     

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors. A cyclic interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w\left(G\right)$ ($w_c\left(G\right)$) and $W\left(G\right)$ ($W_c\left(G\right)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w\left(G\right)$ and $W\left(G\right)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W\left(G\right)\le 1+?\frac{\left|V\left(G\right)\right|}{2}?(\Delta \left(G\right)?1)$. We also give several results towards the general conjecture that $W_c\left(G\right)\le \left|V\left(G\right)\right|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$.     

Total list weighting of graphs with bounded maximum average degree

A proper total weighting of a graph $G$ is a mapping $?$ which assigns to each vertex and each edge of $G$ a real number as its weight so that for any edge $uv$ of $G$, ${\sum }_{e\in E\left(v\right)}?\left(e\right)+?\left(v\right)\ne {\sum }_{e\in E\left(u\right)}?\left(e\right)+?\left(u\right)$. A $(k,k^{\prime })$-list assignment of $G$ is a mapping $L$ which assigns to each vertex $v$ a set $L\left(v\right)$ of $k$ permissible weights and to each edge $e$ a set $L\left(e\right)$ of $k^{\prime }$ permissible weights. An $L$-total weighting is a total weighting $?$ with $?\left(z\right)\in L\left(z\right)$ for each $z\in V\left(G\right)\cup E\left(G\right)$. A graph $G$ is called $(k,k^{\prime })$-choosable if for every $(k,k^{\prime })$-list assignment $L$ of $G$, there exists a proper $L$-total weighting. It was proved in Tang and Zhu (2017) that if $p\in \{5,7,11\}$, a graph $G$ without isolated edges and with $\mathrm{mad}\left(G\right)\le p?1$ is $(1,p)$-choosable. In this paper, we strengthen this result by showing that for any prime $p$, a graph $G$ without isolated edges and with $\mathrm{mad}\left(G\right)\le p?1$ is $(1,p)$-choosable.     

A note on the DP-chromatic number of complete bipartite graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvo?ák and Postle. Several known bounds for the list chromatic number of a graph $G$, ${\chi }_{?}\left(G\right)$, also hold for the DP-chromatic number of $G$, ${\chi }_{DP}\left(G\right)$. On the other hand, there are several properties of the DP-chromatic number that show that it differs with the list chromatic number. In this note we show one such property. It is well known that ${\chi }_{?}\left(K_{k,t}\right)=k+1$ if and only if $t\ge k^k$. We show that ${\chi }_{DP}\left(K_{k,t}\right)=k+1$ if $t\ge 1+(k^k∕k!)(log(k!)+1)$, and we show that ${\chi }_{DP}\left(K_{k,t}\right)<k+1$ if $t<k^k∕k!$.     

Sum choice number of generalized θ-graphs

Let $G=\left(VE\right)$ be a simple graph and for every vertex $v\in V$ let $L\left(v\right)$ be a set (list) of available colors. $G$ is called $L$-colorable if there is a proper coloring $\phi$ of the vertices with $\phi \left(v\right)\in L\left(v\right)$ for all $v\in V$. A function $f:V\to \mathbb{N}$ is called a choice function of $G$ and $G$ is said to be $f$-list colorable if $G$ is $L$-colorable for every list assignment $L$ choice function is defined by $size\left(f\right)={\sum }_{v\in V}f\left(v\right)$ and the sum choice number ${\chi }_{sc}\left(G\right)$ denotes the minimum size of a choice function of $G$.Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For $r\ge 3$ a generalized ${\theta }_{k_1{k}_2\dots k_r}$-graph is a simple graph consisting of two vertices $v_1$ and $v_2$ connected by $r$ internally vertex disjoint paths of lengths $k_1,k_2,\dots ,k_r$ $(k_1\le k_2\le ?\le k_r)$.In 2014, Carraher et al. determined the sum-paintability of all generalized $\theta$-graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized $\theta$-graphs with $k_1\ge 2$ and characterize all generalized $\theta$-graphs $G$ which attain the trivial upper bound $\left|V\left(G\right)\right|+\left|E\left(G\right)\right|$.     

Fractional index convolution complementarity problems

Convolution complementarity problems have the form: given a kernel function $k$ and a function $q$, find a function $u$ such that $u\left(t\right)\ge 0$, $(k1u)\left(t\right)+q\left(t\right)\ge 0$ for (almost) all $t$, and where ${\int }_0^{T}u{\left(t\right)}^T[(k1u)\left(t\right)+q\left(t\right)]dt=0$. A fractional index problem of this kind has $k\left(t\right)\sim K_0{t}^{\alpha -1}$ for $t$ small, with $0<\alpha <1$. Such problems are shown to have unique solutions under mild conditions.     

Degree and neighborhood conditions for hamiltonicity of claw-free graphs

For a graph $H$, let ${\sigma }_t\left(H\right)=min\left\{{\Sigma }_{i=1}^t{d}_H\left(v_i\right)\right|\{v_1,v_2,\dots ,v_t\}\text{is an independent set in }H\}$ and let $U_t\left(H\right)=min\left\{\right|{?}_{i=1}^t{N}_H\left(v_i\right)\left|\right|\{v_1,v_2,?,v_t\}\text{is an independent set in }H\}$. We show that for a given number $?$ and given integers $p\ge t>0$, $k\in \{2,3\}$ and $N=N(p,?)$, if $H$ is a $k$-connected claw-free graph of order $n>N$ with $\delta \left(H\right)\ge 3$ and its Ryjác?ek’s closure $cl\left(H\right)=L\left(G\right)$, and if $d_t\left(H\right)\ge t(n+?)∕p$ where $d_t\left(H\right)\in \{{\sigma }_t\left(H\right),U_t\left(H\right)\}$, then either $H$ is Hamiltonian or $G$, the preimage of $L\left(G\right)$, can be contracted to a $k$-edge-connected $K_3$-free graph of order at most $max\{4p?5,2p+1\}$ and without spanning closed trails. As applications, we prove the following for such graphs $H$ of order $n$ with $n$ sufficiently large:(i) If $k=2$, $\delta \left(H\right)\ge 3$, and for a given $t$ ($1\le t\le 4$) $d_t\left(H\right)\ge \frac{tn}{4}$, then either $H$ is Hamiltonian or $cl\left(H\right)=L\left(G\right)$ where $G$ is a graph obtained from $K_{2,3}$ by replacing each of the degree 2 vertices by a $K_{1,s}$ ($s\ge 1$). When $t=4$ and $d_t\left(H\right)={\sigma }_4\left(H\right)$, this proves a conjecture in Frydrych (2001).(ii) If $k=3$, $\delta \left(H\right)\ge 24$, and for a given $t$ ($1\le t\le 10$) $d_t\left(H\right)>\frac{t(n+5)}{10}$, then $H$ is Hamiltonian. These bounds on $d_t\left(H\right)$ in (i) and (ii) are sharp. It unifies and improves several prior results on conditions involved ${\sigma }_t$ and $U_t$ for the hamiltonicity of claw-free graphs. Since the number of graphs of orders at most $max\{4p?5,2p+1\}$ are fixed for given $p$, improvements to (i) or (ii) by increasing the value of $p$ are possible with the help of a computer.     

On almost everywhere convergence and divergence of Marcinkiewicz-like means of integrable functions with respect to the two-dimensional Walsh system

Let $\left|n\right|$ be the lower integer part of the binary logarithm of the positive integer $n$ and $\alpha :{\mathbb{N}}^2\to {\mathbb{N}}^2$. In this paper we generalize the notion of the two dimensional Marcinkiewicz means of Fourier series of two-variable integrable functions as $t_n^{\alpha }f?\frac{1}{n}{\sum }_{k=0}^{n?1}{S}_{\alpha (\left|n\right|,k)}f$ and give a kind of necessary and sufficient condition for functions in order to have the almost everywhere relation $t_n^{\alpha }f\to f$ for all $f\in L^1\left({[0,1)}^2\right)$ with respect to the Walsh–Paley system. The original version of the Marcinkiewicz means are defined by $\alpha (\left|n\right|,k)=(k,k)$ and discussed by a lot of authors. See for instance [13], [8], [6], [3], [11].     

A sufficient condition for DP-4-colorability

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-choosable. Furthermore, Jin et al. (2016) showed that for each $k\in \{3,4,5,6\}$, every signed planar graph without $C_k$ is signed 4-choosable. In this paper, we show that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-DP-colorable, which is an extension of the above results.