We consider coloring problems inspired by the theory of anti-Ramsey /rainbow colorings that we generalize to a far extent. Let F be a hereditary family of graphs; i.e., if H ∈ F and H ′ ⊂ H then also H ′ ⊂ F . For a graph G and any integer n ≥ | G | , let f ( n , G | F ) denote the smallest number k of colors such that any edge coloring of K n with at least k colors forces a copy of G in which each color class induces a member of F . The case F = { K 2 } is the notorious anti-Ramsey rainbow coloring problem introduced by Erdős, Simonovits and Sós in 1973. Using the F -deck of G , D ( G | F ) = { H : H = G − D , D ∈ F } , we define χ F ( G ) = min { χ ( H ) : H ∈ D ( G | F ) } . The main theorem we prove is: Suppose F is a hereditary family of graphs, and let G be a graph not a member of F . (1) If χ F ( G ) ≥ 3 , then f ( n , G | F ) = ( 1 + o ( 1 ) ) ex ( n , K χ F ( G ) ) . (2) Otherwise f ( n , G | F ) = o ( n 2 ) . Among the families covered by this theorem are: matchings, acyclic graphs, planar and outerplanar graphs, d -degenerate graphs, graphs with chromatic number at most k , graphs with bounded maximum degree, and many more. We supply many concrete examples to demonstrate the wide range of applications of the main theorem; the next result is a representative of these examples. For p ≥ 5 and F = { t K 2 : t ≥ 1 } , we have f ( n , K p | F ) = ( 1 + o ( 1 ) ) ex ( n , K ⌈ p / 2 ⌉ ) ; this is the smallest number of colors such that any edge coloring of K n with this many colors contains a properly colored copy of K p . In other words, a certain number of colors forces nearly twice as large properly edge-colored complete subgraphs as rainbow ones.

Abstract For an integer , a k‐path vertex cover of a graph is a set that shares a vertex with every path subgraph of order k in G. The minimum cardinality of a k‐path vertex cover is denoted by . We give estimates—mostly upper bounds—on in terms of various parameters, including vertex degrees and the number of vertices and edges. The problem is also considered on chordal graphs and planar graphs.

We consider the scheduling model with two identical machines and jobs which arrive online in a list and are assigned to the machines with the objective of minimizing the makespan. Differently from the pure online version, we know in advance a lower bound and also an upper bound on the total size of all jobs. Our algorithm improves previous results on some interval of r, where r is the ratio of the upper and lower bounds on the total size. For most ranges of r our algorithm is best possible. Our technique is based on a smart application of so-called “safe sets”.

A caterpillar is either a K2 or a tree on at least 3 vertices such that deleting its leaves we obtain a path of order at least 1. Given a simple undirected graph G=(V,E), a caterpillar factor of G is a set of caterpillar subgraphs of G such that each vertex v∈V belongs to exactly one of them. A caterpillar factor F is internally even if every vertex of degree degF(v)≥2 has an even degree; F is odd if degF(v) is odd for every v∈V(G). We present a linear-time algorithm that decides whether a tree admits an internally even caterpillar factor and, on the other hand, we prove that the decision problem is NP-complete on the class of planar bipartite graphs. For the odd caterpillar factor problem, we obtain similar results. It can be decided in linear time over the class of trees, but the problem is NP-complete on the class of bipartite graphs.

In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on $$P_t$$ -free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for $$t\le 5$$ (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014, pp 570–581, 2014), and an algorithm for $$t=6$$ announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on $${P}_6$$ -free graphs. CoRR, arXiv:1707.05491 , 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any $$t\ge 1$$ , there is an algorithm for Maximum Independent Set on $$P_t$$ -free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in $$2^{\mathcal {O}(\sqrt{tn \log n})}$$ time on $$P_t$$ -free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. Scattered Set is the generalization of Maximum Independent Set where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-Scattered Set on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges):

Let be a graph and let be a positive weight function on the vertices of G. For every subset X of V, let . A non‐empty subset is a weighted safe set if, for every component C of the subgraph induced by S and every component D of , we have whenever there is an edge between C and D. If the subgraph induced by a weighted safe set S is connected, then the set S is called a weighted connected safe set. In this article, we show that the problem of computing the minimum weight of a safe set is ‐hard for trees, even if the underlying tree is restricted to be a star, but it is polynomially solvable for paths. We also give an time 2‐approximation algorithm for finding a weighted connected safe set with minimum weight in a weighted tree. Then, as a generalization of the concept of a minimum safe set, we define the concept of a parameterized infinite family of proper central subgraphs on weighted trees, whose polar ends are the vertex set of the tree and the centroid points. We show that each of these central subgraphs includes a centroid point.

It is an outstanding open question in algorithmic graph theory to determine the complexity of the MAXIMUM INDEPENDENT SET problem on P_t-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t at most 5 [Lokshtanov et al., SODA 2014, 570-581, 2014]. Here we study the existence of subexponential-time algorithms for the problem: by generalizing an earlier result of Randerath and Schiermeyer for t=5 [Discrete App. Math., 158 (2010), 1041-1044], we show that for any t at least 5, there is an algorithm for MAXIMUM INDEPENDENT SET on P_t-free graphs whose running time is subexponential in the number of vertices. SCATTERED SET is the generalization of MAXIMUM INDEPENDENT SET where the vertices of the solution are required to be at distance at least $d$ from each other. We give a complete characterization of those graphs H for which SCATTERED SET on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges): * If every component of H is a path, then d-SCATTERED SET on H-free graphs with n vertices and m edges can be solved in time 2^{(n+m)^{1-O(1/|V(H)|)}}, even if d is part of the input. * Otherwise, assuming ETH, there is no 2^{o(n+m)} time algorithm for d-SCATTERED SET for any fixed d at least 3 on H-free graphs with n vertices and m edges.

The $\frac{3}{4}$-Game Total Domination Conjecture posed by Henning, Klavžar, and Rall [Combinatorica, (2016)] states that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $\gamma_{tg}(G) \le \frac{3}{4}n$, where $\gamma_{tg}(G)$ denotes the game total domination number of $G$. Motivated by this conjecture, we raise the problem to a higher level by introducing a transversal game in hypergraphs. We define the game transversal number, $\tau_g(H)$, of a hypergraph $H$, and prove that if every edge of $H$ has size at least 2, and $H \ncong C_4$, then $\tau_g(H) \le \frac{4}{11}(n_{_H}+m_{_H})$, where $n_{_H}$ and $m_{_H}$ denote the number of vertices and edges, respectively, in $H$. Further, we characterize the hypergraphs achieving equality in this bound. As an application of this result, we prove that if $G$ is a graph on $n$ vertices with minimum degree at least 2, then $\gamma_{{tg}}(G) < \frac{8}{11} n$. As a consequence of this result, the $\frac{3}{4}$-Game Total Domination Conjecture is true over the class of graphs with minimum degree at least 2.

The leaf graph of a connected graph is obtained by joining a new vertex of degree one to each noncutting vertex. We prove that if a connected graph G is not dominated by any of its induced paths, then G is dominated by a connected induced subgraph whose leaf graph, too, is an induced subgraph of G. It follows that, for every nonempty class ${\cal D}$ of connected graphs, all of the minimal graphs not dominated by any induced subgraph isomorphic to some $D\in{\cal D}$ are cycles (of well-determined lengths) and leaf graphs of some graphs $H\notin{\cal D}$. In particular, if ${\cal D}$ is closed under the operation of taking connected induced subgraphs, then the hereditarily ${\cal D}$-dominated graphs are characterized by the following family of forbidden induced subgraphs: leaf graphs of the connected graphs that are not in ${\cal D}$, but all of their connected induced subgraphs are in ${\cal D}$, and the cycle $C_{t+2}$, where t is the length of the shortest path not in ${\cal D}$ (if ${\cal D}$ does not contain all paths). This solves a problem that was open since the 1980s. A solution for the case of induced-hereditary classes ${\cal D}$ has been found simultaneously by Bacsó by applying a different method.

A ranking of a graph is a coloring of the vertex set with positive integers in such a way that on every path connecting two vertices of the same color there is a vertex of larger color. We consider the directed variant of this problem, where the above condition is imposed only on those paths in which all edges are oriented consecutively. We show that the ranking number of an orientation of a tree is bounded by that of its longest directed path plus one, and that it can be computed in polynomial time. Unlike the undirected case, however, deciding whether the ranking number of a directed (and even of an acyclic directed) graph is bounded by a constant is NP-complete. In fact, the 3-ranking of planar bipartite acyclic digraphs is already hard.

A vertex (edge) coloring $\phi:V\rightarrow \{1,2,\ldots ,t\}$ ($\phi':E\rightarrow \{1,2,\ldots,$ $t\}$) of a graph G=(V,E) is a vertex (edge) t-ranking if, for any two vertices (edges) of the same color, every path between them contains a vertex (edge) of larger color. The {\em vertex ranking number} $\chi_{r}(G)$ ({\em edge ranking number} $\chi_{r}'(G)$) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the {\sc Vertex Ranking} and {\sc Edge Ranking} problems. It is shown that $\chi_{r}(G)$ can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize the graphs where the vertex ranking number $\chi_{r}$ and the chromatic number $\chi$ coincide on all induced subgraphs, show that $\chi_{r}(G)=\chi (G)$ implies $\chi (G)=\omega (G)$ (largest clique size), and give a formula for $\chi_{r}'(K_n)$.

In a given graph with n vertices, a routing is defined as a set of n(n - 1) routes, one route connecting each ordered pair of vertices. The load of a vertex is the number of routes going through it. The forwarding index of the graph is the minimum of the largest load taken over all routings. We construct undirected graphs with a high degree of symmetry and specified diameter, in which the load of every vertex is at most constant times the number of vertices. This gives a partial solution to a problem of Chung et al. [IEEE Trans. Inf. Theory IT-33(2) 224-232 (1987)]. © 1996 John Wiley & Sons, Inc.

The authors present a lower bound on the maximum size of a bipartite subgraph of a triangle-free graph that improves a result due to Erdös and Lovász. It also gives a polynomial-time algorithm, while the previous bound was proved by probabilistic methods.

Abstract Giving a partial solution to a conjecture of Balas and Yu [Networks 19 (1989) 247–235], we prove that if the complement of a graph G on n vertices contains no set of t + 1 pairwise disjoint edges as an induced subgraph, then G has fewer than (n/2t)2t maximal complete subgraphs. © 1993 by John Wiley & Sons, Inc.

A Boolean formula in a conjunctive normal form is called a $(k,s)$ – formula if every clause contains exactly k variables and every variable occurs in at most s clauses. The $(k,s)$–${\text{SAT}}$ problem is the SATISFIABILITY problem restricted to $(k,s)$–formulas. It is proved that for every $k \geqslant 3$ there is an integer $f(k)$ such that $(k,s)$–${\text{SAT}}$ is trivial for $s \leqslant f(k)$ (because every $(k,s)$–formula is satisfiable) and is NP-complete for $s \geqslant f(k) + 1$. Moreover, $f(k)$ grows exponentially with k, namely, $\lfloor {{{2^k } / {ek}}} \rfloor \leqslant f(k) \leqslant 2^{k - 1} - 2^{k - 4} - 1$ for $k \geqslant 4$.

In a graph $G = ( V,E ),E [ v ]$ denotes the set of edges in the subgraph induced by $N [ v ] \equiv \{ v \} \cup \{ u \in V:uv \in E \}$. The neighborhood-covering problem is to find the minimum cardinality of a set C of vertices such that $E = \cup \{ E [ v ]:v \in C \}$. The neighborhood-independence problem is to find the maximum cardinality of a set of edges in which there are no two distinct edges belonging to the same $E [ v ]$ for any $v \in V$. Two other related problems are the clique-transversal problem and the clique-independence problem. It is shown that these four problems are NP-complete in split graphs with degree constraints and linear time algorithms for them are given in a strongly chordal graph when a strong elimination order is given.

In this paper, it is proved that every triangle-free graph on $n \geq 4$ vertices has at most $2^{n /2} $ or $5 \cdot 2^{( n - 5 )/2} $ independent sets maximal under inclusion, whether n is even or odd. In each case, the extremal graph is unique. If the graph is a forest of odd order, then the upper bound can be improved to $2^{( n - 1 )/2} $.

Efficient algorithms for finding Hamiltonian cycles, Hamiltonian paths, and cycles through two given vertices in bipartite tournaments are given.