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...

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.

Let $G=\left(V\right(G),E(G\left)\right)$ be a simple graph and $E_G\left(v\right)$ denote the set of edges incident with a vertex $v$. A neighbor sum distinguishing (NSD) total coloring $\phi$ of $G$ is a proper total coloring of $G$ such that ${\sum }_{z\in E_G\left(u\right)\cup \left\{u\right\}}\phi \left(z\right)\ne {\sum }_{z\in E_G\left(v\right)\cup \left\{v\right\}}\phi \left(z\right)$ for each edge $uv\in E\left(G\right)$. Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree $\Delta$ admits an NSD total $(\Delta +3)$-coloring. We prove that the list version of this conjecture holds for any IC-planar graph with $\Delta \ge 11$ but without $5$-cycles by applying the Combinatorial Nullstellensatz.

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$.

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...

Let $G$ be a connected graph of order $n$ and $U$ a unicyclic graph with the same order. We firstly give a sharp bound for $m_G\left(\mu \right)$, the multiplicity of a Laplacian eigenvalue $\mu$ of $G$. As a straightforward result, $m_U\left(1\right)\le n-2$. We then provide two graph operations (i.e., grafting and shifting) on graph $G$ for which the value of $m_G\left(1\right)$ is nondecreasing. As applications, we get the distribution of $m_U\left(1\right)$ for unicyclic graphs on $n$ vertices. Moreover, for the two largest possible values of $m_U\left(1\right)\in \{n-5,n-3\}$, the corresponding graphs $U$ are...

Let $G$ be a simple graph, let $d\left(v\right)$ denote the degree of a vertex $v$ and let $g$ be a nonnegative integer function on $V\left(G\right)$ with $0\le g\left(v\right)\le d\left(v\right)$ for each vertex $v\in V\left(G\right)$. A $g_c$-coloring of $G$ is an edge coloring such that for each vertex $v\in V\left(G\right)$ and each color $c$, there are at least $g\left(v\right)$ edges colored $c$ incident with $v$. The $g_c$-chromatic index of $G$, denoted by ${\chi }_{g_c}^{\text{'}}\left(G\right)$, is the maximum number of colors such that a $g_c$-coloring of $G$ exists. Any simple graph $G$ has the $g_c$-chromatic index equal to ${\delta }_g\left(G\right)$ or ${\delta }_g\left(G\right)-1$, where ${\delta }_g\left(G\right)={min}_{v\in V\left(G\right)}\lfloor d\left(v\right)/g\left(v\right)\rfloor$. A graph $G$ is nearly bipartite,...

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let $G$ be a bridgeless simple graph with minimum degree at least $3$. Jackson and Yoshimoto (2007) showed that $G$ has an even factor containing two arbitrary prescribed edges. They also proved that $G$ has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges $e_1$ and $e_2$ of $G$, there is an even factor containing $e_1$ and $e_2$...

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g(n,l)$, the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$. By edit distance of two graphs $G$, $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$. This new extremal number $g(n,l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...