A graph $G=(V,E)$ is called improperly $(d_1,\cdots ,d_k)$-colorable if the vertex set $V$ can be partitioned into subsets $V_1,\cdots ,V_k$ such that the graph $G\left[V_i\right]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1\le i\le k$. In this paper, we mainly study the improper coloring of $1$-planar graphs and show that $1$-planar graphs with girth at least $7$ are $(2,0,0,0)$-colorable.

A graph $G$ is $H$-saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$. The saturation number, $\mathrm{sat}(n,H)$, is the minimum number of edges of a graph in the set of all $H$-saturated graphs of order $n$. We determine the saturation number $\mathrm{sat}(n,P_6+t{P}_2)$ for $n\ge \frac{10}{3}t+10$ and characterize the extremal graphs for $n>\frac{10}{3}t+20$.

For a simple graph $G$ on $n$ vertices and an integer $k$ with $1\le k\le n$, denote by ${𝒮}_k^{+}\left(G\right)$ the sum of $k$ largest signless Laplacian eigenvalues of $G$. It was conjectured that ${𝒮}_k^{+}\left(G\right)\le e\left(G\right)+\left(\genfrac{}{}{0pt}{}{k+1}{2}\right)$, where $e\left(G\right)$ is the number of edges of $G$. This conjecture has been proved to be true for all graphs when $k\in \{1,2,n-1,n\}$, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all $k$). In this note, this conjecture is proved to be true for all graphs when $k=n-2$, and for some new classes of graphs.

A graph is called distance integral (or $D$-integral) if all eigenvalues of its distance matrix are integers. In their study of $D$-integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$-integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_1,p_2,p_3}$ with $p_1<p_2<p_3$, and $K_{p_1,p_2,p_3,p_4}$ with $p_1<p_2<p_3<p_4$, as well as the infinite classes of distance integral...

We show that, given any n and α, any embedding of any sufficiently large complete graph in ℝ³ contains an oriented link with components Q₁, ..., Qₙ such that for every i ≠ j, $\left|lk\right(Q_i,Q_j\left)\right|\ge \alpha$ and $\left|a₂\right(Q_i\left)\right|\ge \alpha$, where $a₂\left(Q_i\right)$ denotes the second coefficient of the Conway polynomial of $Q_i$.

The line graph of a graph $G$, denoted by $L\left(G\right)$, has $E\left(G\right)$ as its vertex set, where two vertices in $L\left(G\right)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$, define ${\overline{\sigma }}_2\left(H\right)=min\{d\left(u\right)+d\left(v\right):uv\in E\left(H\right)\}$. Let $H$ be a 2-connected claw-free simple graph of order $n$ with $\delta \left(H\right)\ge 3$. We show that, if ${\overline{\sigma }}_2\left(H\right)\ge \frac{1}{7}(2n-5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček’s closure $\mathrm{cl}\left(H\right)=L\left(G\right)$, where $G$ is an essentially $2$-edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

For any collection of graphs $G₁,...,G_N$ we find the minimal dimension d such that the product $G₁\times ...\times G_N$ is embeddable into ${ℝ}^d$ (see Theorem 1 below). In particular, we prove that (K₅)ⁿ and $\left(K_{3,3}\right)ⁿ$ are not embeddable into ${ℝ}^{2n}$, where K₅ and $K_{3,3}$ are the Kuratowski graphs. This is a solution of a problem of Menger from 1929. The idea of the proof is a reduction to a problem from so-called Ramsey link theory: we show that any embedding $LkO\to S^{2n-1}$, where O is a vertex of (K₅)ⁿ, has a pair of linked (n-1)-spheres.

Given a graph $G$, let $f\left(G\right)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f\left(G\right)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. In this paper we prove that $f(m,{\theta }_{k,s})\ge \frac{1}{2}m+\Omega \left(m^{(2k+1)/(2k+2)}\right)$, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K_k^{\text{'}}$ and $K_{t,s}^{\text{'}}$ for the subdivisions of $K_k$ and $K_{t,s}$. We show that $f(m,K_k^{\text{'}})\ge \frac{1}{2}m+\Omega \left(m^{(5k-8)/(6k-10)}\right)$ and $f(m,K_{t,s}^{\text{'}})\ge \frac{1}{2}m+\Omega \left(m^{(5t-1)/(6t-2)}\right)$, improving a result of Q. Zeng, J. Hou. We also give lower bounds on...

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph $G$, a hereditary graph property $𝒫$ and $l\ge 1$ we define ${\chi }_{𝒫,l}^{\text{'}}\left(G\right)$ to be the minimum number of colours needed to properly colour the edges of $G$, such that any subgraph of $G$ induced by edges coloured by (at most) $l$ colours is in $𝒫$. We present a necessary and sufficient condition for the existence of ${\chi }_{𝒫,l}^{\text{'}}\left(G\right)$. We focus on edge-colourings of graphs with respect to the hereditary...

The generalized $k$-connectivity ${\kappa }_k\left(G\right)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as ${\lambda }_k\left(G\right)=min\{\lambda \left(S\right):S\subseteq V\left(G\right)$ and $\left|S\right|=k\}$, where $\lambda \left(S\right)$ denotes the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $S\subseteq V\left(T_i\right)$ for $1\le i\le \ell$. In this paper we prove that for any two connected graphs $G$ and $H$ we have ${\lambda }_3(G\square H)\ge {\lambda }_3\left(G\right)+{\lambda }_3\left(H\right)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also...

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number ${\chi }_D\left(G\right)$ of G. Extending these concepts to infinite graphs we prove that $D\left(Q_{\aleph }₀\right)=2$ and ${\chi }_D\left(Q_{\aleph }₀\right)=3$, where $Q_{\aleph }₀$ denotes the hypercube of countable dimension. We also show that ${\chi }_D\left(Q₄\right)=4$, thereby completing the investigation of finite hypercubes with respect to ${\chi }_D$. Our...