For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). Note that if H is the triangle, then H-colorings are equivalent to 3-colorings. In this paper we are interested in the case that H is the five-vertex cycle C₅. A minimal obstruction to C₅-coloring is a graph that does not have a C₅-coloring, but every proper induced subgraph thereof has a C₅-coloring. In this paper we are interested in minimal obstructions to C₅-coloring in F-free graphs, i.e., graphs that exclude some fixed graph F as an induced subgraph. Let P_t denote the path on t vertices, and let S_{a,b,c} denote the graph obtained from paths P_{a+1},P_{b+1},P_{c+1} by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to C₅-coloring among F-free graphs, where F ∈ {P₈, S_{2,2,1}, S_{3,1,1}} and explicitly determine all such obstructions. This extends the results of Kamiński and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of P₇-free minimal obstructions to C₅-coloring, and of Dębski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique S_{2,1,1}-free minimal obstruction to C₅-coloring. We complement our results with a construction of an infinite family of minimal obstructions to C₅-coloring, which are simultaneously P_{13}-free and S_{2,2,2}-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.

In the 1960s, Erdös and Pósa proved that there is a packing-covering duality for cycles in graphs. As part of the graph minor project, Robertson and Seymour greatly extended this: there is such a duality for $H$-expansions in graphs if and only if $H$ is a planar graph (this includes the previous result for $H=K_3$). We consider vertex labeled graphs and minors and provide such a characterization for 2-connected labeled graphs $H$. In particular, this generalizes results of Kakimura, Kawarabayashi and Marx [ J. Combin. Theory Ser. B, 101 (2011), pp. 378--381] and Huynh, Joos, and Wollan [ Combinatorica, 39 (2019), pp. 91--133] up to weaker dependencies of the parameters.

Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We consider the task of adding a minimum-cost edge-set to the graph such that the adversary never wins. We show that this problem is equivalent to covering a digraph with nontrivial strongly connected components at minimal cost. We provide efficient exact and approximation algorithms for this task. In particular, for the unit-cost problem, we give a $\log_2 n$-factor approximation algorithm and a polynomial-time algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter algorithm for the problem parameterized by the treewidth of the input graph. For general nonnegative weights we give tight upper and lower approximation bounds relative to the directed Steiner forest problem. Additionally, we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. To obtain our results, we exploit a close relation to the classical strong connectivity augmentation problem as well as directed Steiner problems.

A graph is $H$-free if it has no induced subgraph isomorphic to $H$. We characterize all graphs $H$ for which there are only finitely many minimal non-3-colorable $H$-free graphs. Such a characterization was previously known only in the case when $H$ is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs $H$ for which there are only finitely many $H$-free minimal obstructions for list 3-colorability.

In a Stackelberg Pricing Game a distinguished player, the leader, chooses prices for a set of items, and the other players, the followers, each seeks to buy a minimum cost feasible subset of the items. The goal of the leader is to maximize her revenue, which is determined by the sold items and their prices. Most previously studied cases of such games can be captured by a combinatorial model where we have a base set of items, some with fixed prices, some priceable, and constraints on the subsets that are feasible for each follower. In this combinatorial setting, Briest et al. and Balcan et al. independently showed that the maximum revenue can be approximated to a factor of H_k ~ log(k), where k is the number of priceable items. Our results are twofold. First, we strongly generalize the model by letting the follower minimize any continuous function plus a linear term over any compact subset of R_(n>=0); the coefficients (or prices) in the linear term are chosen by the leader and determine her revenue. In particular, this includes the fundamental case of linear programs. We give a tight lower bound on the revenue of the leader, generalizing the results of Briest et al. and Balcan et al. Besides, we prove that it is strongly NP-hard to decide whether the optimum revenue exceeds the lower bound by an arbitrarily small factor. Second, we study the parameterized complexity of computing the optimal revenue with respect to the number k of priceable items. In the combinatorial setting, given an efficient algorithm for optimal follower solutions, the maximum revenue can be found by enumerating the 2^k subsets of priceable items and computing optimal prices via a result of Briest et al., giving time O(2^k|I|^c ) where |I| is the input size. Our main result here is a W[1]-hardness proof for the case where the followers minimize a linear program, ruling out running time f(k)|I|^c unless FPT = W[1] and ruling out time |I|^o(k) under the Exponential-Time Hypothesis.

We show that for any coloring of the edges of the complete bipartite graph $K_{n,n}$ with three colors there are five disjoint monochromatic cycles which together cover all but $o(n)$ of the vertices. In the same situation, 18 disjoint monochromatic cycles together cover all vertices.

In committee elections it is often assumed that voters only (dis)approve of each candidate or that they rank all candidates, as it is common for single-winner elections. We suggest an intermediate approach, where the voters rank the candidates into a fixed number of groups. This allows more diverse votes than approval votes, but leaves more freedom than in a linear order. A committee is then elected by applying the minisum or minimax approach to minimize the voters' dissatisfaction. We study the axiomatic properties of these committee election rules as well as the complexity of winner determination and show fixed-parameter tractability for our minimax rules.

The complexity of coloring graphs without long induced paths is a notorious problem in algorithmic graph theory, an especially intruiging case being that of 3-colorability. So far, not much was known about certification in this context. We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-coloring P6-free graphs, which solves an open problem posed by Golovach et al. Here, P6 denotes the induced path on six vertices. Our result leads to the following dichotomy theorem: if H is a connected graph, then there are finitely many 4-critical H-free graphs if and only if H is a subgraph of P6. This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand.

A graph is called $t$-perfect if its stable set polytope is defined by nonnegativity, edge, and odd-cycle inequalities. We show that it can be decided in polynomial time whether a given claw-free graph is $t$-perfect.