For a countable bounded principal ideal poset \(P\) and a natural number \(r\), there exists a countable bounded principal ideal poset \(P’\) such that for an arbitrary \(r\)-colouring of the points (resp. two-chains) of \(P’\), a monochromatically embedded copy of \(P\) can be found in \(P’\). Moreover, a best possible upper bound for the height of \(P’\) in terms of \(r\) and the height of \(P\) is given.

A vertex set \(S \subseteq V(G)\) is a perfect code or efficient dominating set for a graph \(G\) if each vertex of \(G\) is dominated by \(S\) exactly once. Not every graph has an efficient dominating set, and the efficient domination number \(F(G)\) is the maximum number of vertices one can dominate given that no vertex is dominated more than once. That is, \(F(G)\) is the maximum influence of a packing \(S \subseteq V(G)\). In this paper, we begin the study of \(LF(G)\), the lower efficient domination number of \(G\), which is the minimum number of vertices dominated by a maximal packing. We show that the decision problem associated with deciding if \(LF(G) \leq K\) is an NP-complete problem. The principal result is a characterization of trees \(T\) where \(LF(T) = F(T)\).

We introduce a new class of colorings of graphs and define and study two new graph coloring parameters. A \({coloring}\) of a graph \(G = (V,E)\) is a partition \(\Pi = \{V_1, V_2, \ldots, V_k\}\) of the vertices of \(G\) into independent sets \(V_i\), or \({color\; classes}\). A vertex \(v_i \in V_i\) is called \({colorful}\) if it is adjacent to at least one vertex in every color class \(V_j\), \(i \neq j\). A \({fall \;coloring}\) is a coloring in which every vertex is colorful. If a graph \(G\) has a fall coloring, we define the \({fall\; chromatic\; number}\) (\({fall \;achromatic\; number}\)) of \(G\), denoted \(\chi_f(G)\), (\(\psi_f(G)\)) to equal the minimum (maximum) order of a fall coloring of \(G\), respectively. In this paper, we relate fall colorings to other colorings of graphs and to independent dominating sets in graphs.

This paper revises Park’s proof of Shannon inequality and also gives a new simple proof.

For \(\pi\) one of the upper domination parameters \(\beta\), \(\Gamma\), or \(IR\), we investigate graphs for which \(\pi\) decreases ( \(\pi\)-edge-critical graphs) and graphs for which \(\pi\) increases ( \(\pi^+\)-edge-critical graphs) whenever an edge is added. We find characterisations of \(\beta\)- and \(\Gamma\)-edge-critical graphs and show that a graph is \(IR\)-edge-critical if and only if it is \(\Gamma\)-edge-critical. We also exhibit a class of \(\Gamma^+\)-edge-critical graphs.

For a graph \(G = (V, E)\), a set \(S \subseteq V\) is a \(k\)-packing if the distance between every pair of distinct vertices in \(S\) is at least \(k+1\), and \(\rho_k(G)\) is the maximum cardinality of a \(k\)-packing. A set \(S \subseteq V\) is a distance-\(k\) dominating set if for each vertex \(u \in V – S\), the distance \(d(u, v) \leq k\) for some \(v \in S\). Call a vertex set \(S\) a \(k\)-independent dominating set if it is both a \(k\)-packing and a distance-\(k\) dominating set, and let the \(k\)-independent domination number \(i_k(G)\) be the minimum cardinality of a \(k\)-independent dominating set. We show that deciding if a graph \(G\) is not \(k\)-equipackable (that is, \(i_k(G) < \rho_k(G)\)) is an NP-complete problem, and we present a lower bound on \(i_k(G)\). Our main result shows that the sequence \((i_1(G), i_2(G), i_3(G), \ldots)\) is surprisingly not monotone. In fact, the difference \(i_{k+1}(G) – i_k(G)\) can be arbitrarily large.

Corresponding to chessboards, we introduce game boards with triangles or hexagons as cells and chess-like pieces for these boards. The independence number \(\beta\) is determined for many of these pieces.

We study the discrepancies of set systems whose incidence matrices are encoded by binary strings which are complex in the sense of Kolmogorov-Chaitin. We show that these systems display an optimal degree of irregularity of distribution.

We use the idea of compressibility to examine the discrepancy of set systems coded by complex sequences.

A multigraph is irregular if no two of its vertices have the same degree. It is known that every graph \(G\) with at most one trivial component and no component isomorphic to \(K_2\) is the underlying graph of some irregular multigraph. The irregularity cost of a graph with at most one trivial component and no component isomorphic to \(K_2\) is defined by \(ic(G) = \min\{|{E}(H)| – |{E}(G)| \mid H\)  is an irregular multigraph containing  G as underlying graph}. It is shown that if \(T\) is a tree on \(n\) vertices, then

\[\frac{n^2-3n+4}{4}\quad \leq \quad ic(T) \leq \binom{n-1}{2}\: \text{if}\: n\equiv0 \;\text{or}\; 3\pmod{4} \; \text{and}\]
\[\frac{n^2-3n+6}{4}\quad \leq \quad ic(T) \leq \binom{n-1}{2}\: \text{if}\: n\equiv1 \;\text{or}\; 2\pmod4 \]
Furthermore, these bounds are shown to be sharp.