The irregularity strength and cost of the union of cliques

Assign positive integer weights to the edges of a simple graph with no component isomorphic to K₁ or K₂, in such a way that the graph becomes irregular, i.e., the weight sums at the vertices become pairwise distinct. The minimum of the largest weights assigned over all such irregular assignments on the vertex-disjoint union of complete graphs is determined. The method of proof also yields the smallest possible total increase in the sum of edge weights in irregular asignments, called irregularity cost.     

Algorithmic complexity of list colorings

Given a graph G = (V,E) and a finite set L(v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f:V → _vεVL(V) such that (i) f(v)εL(v) for each vεV and (ii) f(u) ≠f(v) whenever u, vεV and uvεE. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L(v) has at most three elements, (2) each “color” xε_vεVL(v) occurs in at most three sets L(v), (3) each vertex vεV has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too.     

Rainbow subgraphs in properly edge-colored graphs

We prove that there exist graphs G with arbitrarily large girth such that every proper edge coloring of G contains a rainbow cycle (i.e., a cycle having no pair of monochromatic edges). This answers a problem raised by J. Spencer more than 10 years ago.     

Improved lower bounds on k-independence

A vertex set Y in a (hyper)graph is called k-independent if in the sub(hyper)-graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k-independent set—in terms of degree sequences—which strengthens and generalizes several previously known results, including Turán's theorem.     

A combinatorial problem related to sparse systems of equations

Nowadays sparse systems of equations occur frequently in science and engineering. In this contribution we deal with sparse systems common in cryptanalysis. Given a cipher system, one converts it into a system of sparse equations, and then the system is solved to retrieve either a key or a plaintext. Raddum and Semaev proposed new methods for solving such sparse systems common in modern ciphers which are combinations of linear layers and small S-boxes. It turns out that the solution of a combinatorial MaxMinMax problem provides an upper bound on the average computational complexity of those methods. In this paper we initiate the study of a linear algebra variation of the MaxMinMax problem. The complexity bound proved in this paper significantly overcomes conjectured complexity bounds for Gröbner basis type algorithms.     

The most vital nodes with respect to independent set and vertex cover

Given an undirected graph with weights on its vertices, the k most vital nodes independent set (k most vital nodes vertex cover) problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets (minimum weight of vertex covers, respectively). We also consider the complementary problems, minimum node blocker independent set (minimum node blocker vertex cover) that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets (minimum weight of vertex covers, respectively) in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on cographs and graphs of bounded treewidth. Results on the non-existence of ptas are presented, too.     

[1,1,t]-Colorings of Complete Graphs

Given non-negative integers $r, s,$ and $t,$ an $[r,s,t]$ -coloring of a graph $G = (V(G),E(G))$ is a mapping $c$ from $V(G) \cup E(G)$ to the color set $\{1,\ldots ,k\}$ such that $\left|c(v_i) - c(v_j)\right| \ge r$ for every two adjacent vertices $v_i,v_j, \left|c({e_i}) - c(e_j)\right| \ge s$ for every two adjacent edges $e_i,e_j,$ and $\left|c(v_i) - c(e_j)\right| \ge t$ for all pairs of incident vertices and edges, respectively. The $[r,s,t]$ -chromatic number $\chi _{r,s,t}(G)$ of $G$ is defined to be the minimum $k$ such that $G$ admits an $[r,s,t]$ -coloring. In this note we examine $\chi _{1,1,t}(K_p)$ for complete graphs $K_p.$ We prove, among others, that $\chi _{1,1,t}(K_p)$ is equal to $p+t-2+\min \{p,t\}$ whenever $t \ge \left\lfloor {\frac{p}{2}}\right\rfloor -1,$ but is strictly larger if $p$ is even and sufficiently large with respect to $t.$ Moreover, as $p \rightarrow \infty $ and $t=t(p),$ we asymptotically have $\chi _{1,1,t}(K_p)=p+o(p)$ if and only if $t=o(p).$      

Saturated graphs with minimal number of edges

Let F = {F₁,…} be a given class of forbidden graphs. A graph G is called F-saturated if no F_i ∈ F is a subgraph of G but the addition of an arbitrary new edge gives a forbidden subgraph. In this paper the minimal number of edges in F-saturated graphs is examined. General estimations are given and the structure of minimal graphs is described for some special forbidden graphs (stars, paths, m pairwise disjoint edges).