A \emph{mixed interval graph} is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph $G$, an interval $u$ receives a lower (different) color than an interval $v$ if $G$ contains arc $(u,v)$ (edge $\{u,v\}$). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. For coloring general mixed interval graphs, we present a $\min \{ω(G), λ(G)+1 \}$-approximation algorithm, where $ω(G)$ is the size of a largest clique and $λ(G)$ is the length of a longest directed path in $G$. For the subclass of \emph{bidirectional interval graphs} (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs. We introduce a new natural class of mixed interval graphs, which we call \emph{containment interval graphs}. In such a graph, there is an arc $(u,v)$ if interval $u$ contains interval $v$, and there is an edge $\{u,v\}$ if $u$ and $v$ overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring.

In DDoS attack (Distributed Denial of Service), an attacker gains control of many network users by a virus.Then the controlled users send many requests to a victim, leading to lack of its resources.DDoS attacks are hard to defend because of distributed nature, large scale and various attack techniques.One of possible ways of defense is to place sensors in the network that can detect and stop an unwanted request.However, such sensors are expensive so there is a natural question about a minimum number of sensors and their optimal placement to get the required level of safety.We present two mixed integer models for optimal sensor placement against DDoS attacks.Both models lead to a tradeoff between the number of deployed sensors and the volume of uncontrolled flow.Since above placement problems are NP-hard, two efficient heuristics are designed, implemented and compared experimentally with exact linear programming solvers.

In this paper we give a family of online algorithms for the classical coloring and the $L(2,1)$-labeling problems of unit disk intersection graphs. In the $L(2,1)$-labeling we ask for an assignment of nonnegative integers to the vertices of the input graph, such that adjacent vertices get labels that differ by at least 2, and vertices with a common neighbor get different labels. In particular, we present a coloring algorithm with competitive ratio less than 5, which makes it the currently best online coloring algorithm for unit disk intersection graphs. Our algorithms make use of a geometric representation of such graphs and are inspired by previous results but have better competitive ratios. The improvement comes from a novel application of a fractional and a $b$-fold coloring of the plane, which is in turn a variation of the Hadwiger--Nelson problem. Our method can also be adapted successfully for other classes of geometric intersection graphs.

We present results referring to the Hadwiger–Nelson problem which asks for the minimum number of colors needed to color the plane with no two points at distance 1 having the same color. Exoo considered a more general problem concerning graphs $$G_{[a,b]}$$ with $$\mathbb {R}^2$$ as the vertex set and two vertices adjacent if their distance is in the interval [a, b]. Exoo conjectured $$\chi (G_{[a,b]}) = 7$$ for sufficiently small but positive difference between a and b. We partially answer this conjecture by proving that $$\chi (G_{[a,b]}) \geqslant 5$$ for $$b > a$$ . A j-fold coloring of a graph $$G = (V,E)$$ is an assignment of j-elemental sets of colors to the vertices of G, in such a way that the sets assigned to any two adjacent vertices are disjoint. The fractional chromatic number $$\chi _f(G)$$ is the infimum of fractions k / j for j-fold coloring of G using k colors. We generalize a method by Hochberg and O’Donnel (who proved that $$G_{[1,1]} \leqslant 4.36$$ ) for the fractional coloring of graphs $$G_{[a,b]}$$ , obtaining a bound dependent on $$\frac{a}{b}$$ . We also present few specific and two general methods for j-fold coloring of $$G_{[a,b]}$$ for small j, in particular for $$G_{[1,1]}$$ and $$G_{[1,2]}$$ . The j-fold coloring for small j has strong practical motivation especially in scheduling theory, while graph $$G_{[1,2]}$$ is often used to model hidden conflicts in radio networks.