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=(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$ 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 edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$, denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $\mathrm{pc}\left(G\right)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$-coloring for a connected bipartite graph $G$ having $\delta \left(G\right)\ge 2$ and a dominating...

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

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 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 d-uniform hypergraph is a sum hypergraph iff there is a finite S ⊆ IN⁺ such that is isomorphic to the hypergraph ${⁺}_d\left(S\right)=(V,)$, where V = S and $=v₁,...,v_d:\left(i\ne j\Rightarrow v_i\ne v_j\right)\wedge {\sum }_{i=1}^d{v}_i\in S$. For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $w₁,...,w_{\sigma }\notin V$ such that $\cup w₁,...,w_{\sigma }$ is a sum hypergraph. In this paper, we prove $\sigma {(}_{n₁,...,n_d}^d)=1+{\sum }_{i=1}^d(n_i-1)+min0,\lceil 1/2({\sum }_{i=1}^{d-1}(n_i-1)-n_d)\rceil$, where ${}_{n₁,...,n_d}^d$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.

A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle in $G$. In other words, each cycle of $G$ must be colored with at least three colors. Given a list assignment $L=\left\{L\right(v):v\in V\}$, if there exists an acyclic coloring $\pi$ of $G$ such that $\pi \left(v\right)\in L\left(v\right)$ for all $v\in V$, then we say that $G$ is acyclically $L$-colorable. If $G$ is acyclically $L$-colorable for any list assignment $L$ with $\left|L\right(v\left)\right|\ge k$ for all $v\in V$, then $G$ is acyclically $k$-choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without...

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

A vertex $k$-coloring of a graph $G$ is a if $M\left(u\right)\ne M\left(v\right)$ for every edge $uv\in E\left(G\right)$, where $M\left(u\right)$ and $M\left(v\right)$ denote the multisets of colors of the neighbors of $u$ and $v$, respectively. The minimum $k$ for which $G$ has a multiset $k$-coloring is the ${\chi }_m\left(G\right)$ of $G$. For an integer $\ell \ge 0$, the $\ell$- of a graph $G$, ${\mathrm{cor}}^{\ell }\left(G\right)$, is the graph obtained from $G$ by adding, for each vertex $v$ in $G$, $\ell$ new neighbors which are end-vertices. In this paper, the multiset chromatic numbers are determined for $\ell$- of all complete graphs, the regular complete...

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