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.

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.

We prove: (1) that $c{h}_P\left(G\right)-{\chi }_P\left(G\right)$ can be arbitrarily large, where $c{h}_P\left(G\right)$ and ${\chi }_P\left(G\right)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.

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

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.

We consider, for a positive integer $k$, induced subgraphs in which each component has order at most $k$. Such a subgraph is said to be $k$-divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$-divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for...

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

A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph ${}_{d̲,\left[d̅\right]}\left(S\right)=(V,)$ where V = S and $=e\subseteq S:d̲\le \left|e\right|\le \left[d̅\right]\wedge {\sum }_{v\in e}v\in S$. For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $y₁,...,y_{\sigma }\notin V$ such that $\cup y₁,...,y_{\sigma }$ is a sum hypergraph. Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings...

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

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

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

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

For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{All}$, $E_{Some}$, $E_{None}$ of the edge set E, where: $E_{All}$ = e ∈ E, e belongs to all optimum solutions, $E_{None}$ = e ∈ E, e does not belong to any optimum solution and $E_{Some}$ = e ∈ E, e belongs to some but not to all optimum solutions.