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

A proper coloring $c:V\left(G\right)\to \{1,2,...,k\}$, $k\ge 2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c^{\text{'}}:E\left(G\right)\to \{1,2,...,k-1\}$ defined by $c^{\text{'}}\left(uv\right)=|c\left(u\right)-c\left(v\right)|$ for each edge $uv$ of $G$ is also proper. The minimum integer $k$ for which $G$ has a graceful $k$-coloring is the graceful chromatic number ${\chi }_g\left(G\right)$. It is known that if $T$ is a tree with maximum degree $\Delta$, then ${\chi }_g\left(T\right)\le \lceil \frac{5}{3}\Delta \rceil$ and this bound is best possible. It is shown for each integer $\Delta \ge 2$ that there is an infinite class of trees $T$ with maximum degree $\Delta$ such that ${\chi }_g\left(T\right)=\lceil \frac{5}{3}\Delta \rceil$. In particular, we investigate for each...

A structure $={(A;E_i)}_{i\in n}$ where each $E_i$ is an equivalence relation on A is called an n-grid if any two equivalence classes coming from distinct $E_i$’s intersect in a finite set. A function χ: A → n is an acceptable coloring if for all i ∈ n, the ${\chi }^{-1}\left(i\right)$ intersects each $E_i$-equivalence class in a finite set. If B is a set, then the n-cube Bⁿ may be seen as an n-grid, where the equivalence classes of $E_i$ are the lines parallel to the ith coordinate axis. We use elementary submodels of the universe to characterize...

Let us denote by $\Phi (\lambda ,\mu )$ the statement that $𝔹\left(\lambda \right)=D{\left(\lambda \right)}^{\omega }$, i.e. the Baire space of weight $\lambda$, has a coloring with $\mu$ colors such that every homeomorphic copy of the Cantor set $ℂ$ in $𝔹\left(\lambda \right)$ picks up all the $\mu$ colors. We call a space $X$ $\pi$-regular if it is Hausdorff and for every nonempty open set $U$ in $X$ there is a nonempty open set $V$ such that $\overline{V}\subset U$. We recall that a space $X$ is called feebly compact if every locally finite collection of open sets in $X$ is finite. A Tychonov space is pseudocompact if and...

We investigate the question whether a system ${\left(E_i\right)}_{i\in I}$ of homogeneous linear equations over $\mathbb{Z}$ is non-trivially solvable in $\mathbb{Z}$ provided that each subsystem ${\left(E_j\right)}_{j\in J}$ with $\left|J\right|\le c$ is non-trivially solvable in $\mathbb{Z}$ where $c$ is a fixed cardinal number such that $c<\left|I\right|$. Among other results, we establish the following. (a) The answer is ‘No’ in the finite case (i.e., $I$ being finite). (b) The answer is ‘No’ in the denumerable case (i.e., $\left|I\right|={\aleph }_0$ and $c$ a natural number). (c) The answer in case that $I$ is uncountable and $c\le {\aleph }_0$ is ‘No...

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.

In set theory without the axiom of choice ($\mathrm{AC}$), we study certain non-constructive properties of infinite-dimensional vector spaces. Among several results, we establish the following: (i) None of the principles AC${}^{\mathrm{LO}}$ (AC for linearly ordered families of nonempty sets)—and hence AC${}^{\mathrm{WO}}$ (AC for well-ordered families of nonempty sets)— $\mathrm{DC}(<\kappa )$ (where $\kappa$ is an uncountable regular cardinal), and “for every infinite set $X$, there is a bijection $f:X\to \{0,1\}\times X$”, implies the statement “there exists a field $F$ such that...

We prove that if $X$ is a first countable space with property $\left(DC\left({\omega }_1\right)\right)$ and with a $G_{\delta }$-diagonal then the cardinality of $X$ is at most $𝔠$. We also show that if $X$ is a first countable, DCCC, normal space then the extent of $X$ is at most $𝔠$.

For graphs $G$, $F_1$, $F_2$, we write $G\to (F_1,F_2)$ if for every red-blue colouring of the edge set of $G$ we have a red copy of $F_1$ or a blue copy of $F_2$ in $G$. The size Ramsey number $\widehat{r}(F_1,F_2)$ is the minimum number of edges of a graph $G$ such that $G\to (F_1,F_2)$. Erdős and Faudree proved that for the cycle $C_n$ of length $n$ and for $t\ge 2$ matchings $t{K}_2$, the size Ramsey number $\widehat{r}(t{K}_2,C_n)<n+(4t+3)\sqrt{n}$. We improve their upper bound for $t=2$ and $t=3$ by showing that $\widehat{r}(2K_2,C_n)\le n+2\sqrt{3n}+9$ for $n\ge 12$ and $\widehat{r}(3K_2,C_n)<n+6\sqrt{n}+9$ for $n\ge 25$.

Given a graph $G=(V,E)$, if we can partition the vertex set $V$ into two nonempty subsets $V_1$ and $V_2$ which satisfy $\Delta \left(G\left[V_1\right]\right)\le d_1$ and $\Delta \left(G\left[V_2\right]\right)\le d_2$, then we say $G$ has a $({\Delta }_{d_1},{\Delta }_{d_2})$-partition. And we say $G$ admits an $(F_{d_1},F_{d_2})$-partition if $G\left[V_1\right]$ and $G\left[V_2\right]$ are both forests whose maximum degree is at most $d_1$ and $d_2$, respectively. We show that every planar graph with girth at least 5 has an $(F_4,F_4)$-partition.

The Ramsey number $R(G,H)$ for a pair of graphs $G$ and $H$ is defined as the smallest integer $n$ such that, for any graph $F$ on $n$ vertices, either $F$ contains $G$ or $\overline{F}$ contains $H$ as a subgraph, where $\overline{F}$ denotes the complement of $F$. We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers $R(K_1+L_n,P_m)$ and $R(K_1+L_n,C_m)$ for some integers $m$, $n$, where $L_n$ is...

Let a space $X$ be Tychonoff product ${\prod }_{\alpha <\tau }{X}_{\alpha }$ of $\tau$-many Tychonoff nonsingle point spaces $X_{\alpha }$. Let Suslin number of $X$ be strictly less than the cofinality of $\tau$. Then we show that every point of remainder is a non-normality point of its Čech–Stone compactification $\beta X$. In particular, this is true if $X$ is either $R^{\tau }$ or ${\omega }^{\tau }$ and a cardinal $\tau$ is infinite and not countably cofinal.

We show that given infinite sets $X,Y$ and a function $f:X\to Y$ which is onto and $n$-to-one for some $n\in \mathbb{N}$, the preimage of any ultrafilter $ℱ$ of $Y$ under $f$ extends to an ultrafilter. We prove that the latter result is, in some sense, the best possible by constructing a permutation model $ℳ$ with a set of atoms $A$ and a finite-to-one onto function $f:A\to \omega$ such that for each free ultrafilter of $\omega$ its preimage under $f$ does not extend to an ultrafilter. In addition, we show that in $ℳ$ there exists an ultrafilter compact...

We show that ${\omega }^{*}\setminus \left\{p\right\}$ is not normal, if $p$ is a limit point of some countable subset of ${\omega }^{*}$, consisting of points of character ${\omega }_1$. Moreover, such a point $p$ is a Kunen point and a super Kunen point.