The generalized min-cost flow problem is a variation of the classical min-cost flow problem with losses on the arcs. In contrast to the classical problem, the flow amount is multiplied with the arc loss when traversing an arc. The formulation is motivated by the modelling of energy systems where losses arise naturally. When applying a column generation approach on a path-based formulation, the pricing problem has the structure of a shortest path problem with losses. Due to the multiplicative behavior of these losses, a classical shortest path algorithm cannot be used to generate paths. In particular, the costs on arcs depend on previously selected arcs and their respective losses. The pricing problem can be solved via a dynamic programming scheme. Based on the corresponding Bellman equation, we formulate conditions on the input data under which the dynamic programming algorithm correctly computes the shortest paths. Additionally, we compare the performance of the column generation approach with other solution methods in practice.

For each integer $r\ge 2$ 2, an $r$-graph is an $r$-regular graph in which every odd set of vertices is connected to its complement by at least r edges. Being an $r$-graph is a necessary condition for an $r$-regular graph to be $r$-edge-colorable. On the other hand, for every $r\ge 3$ there exist $r$-graphs in which every two perfect matchings intersect. We show that for every $1<k<r$ it is NP- complete to decide whether a given $r$-graph has $k$-pairwise disjoint perfect matchings. Furthermore, some results concerning the relation between the edge-connectivety and the number of pairwise disjoint perfect matchings in $r$-graphs will be discussed.

We consider injective edge colouring problem, a theoretical model for a packet radio network problem, in which the goal is to assign communication frequencies to network node pairs in a way that eliminates secondary interference. Given a graph G an edge colouring c is injective if for all edges e and e' both incident to a third edge e'', c(e) is not equal to c(e'). The injective chromatic index of G is the least k such that G admits an injective k-edge colouring. We prove that the injective chromatic index of a graph with maximum degree D and degeneracy d is at most big-O of d cubed times log(D), and that the injective chromatic index of a graph of Euler genus g is at most (3+o(1))g. The upper bound for Euler genus is tight up to the choice of lower order term when G is a clique. We will spend any remaining time exploring how we use the ideas from these proofs to bound the oriented chromatic number above by a polynomial in Euler genus.

Joint work with Peter Bradshaw (University of Illinois Urbana Champaign), and Jingwei Xu (University of Illinois Urbana Champaign).

An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Let $G$ and $H$ be $r$-graphs. An \emph{$H$-coloring} of $G$ is a mapping
$f:E(G)\to E(H)$ such that each $r$ adjacent edges of $G$ are mapped to $r$ adjacent edges of $H$. For every $r\ge 3$, let ${\mathcal{H}}_r$ be an inclusion-wise minimal set of connected $r$-graphs, such that for every connected $r$-graph $G$ there is an $H\in {\mathcal{H}}_r$ which colors $G$.

We show that ${\mathcal{H}}_r$ is unique and characterize ${\mathcal{H}}_r$ by showing that
$G\in {\mathcal{H}}_r$ if and only if the only connected $r$-graph coloring $G$ is $G$ itself.

The Petersen Coloring Conjecture states that the Petersen graph $P$ colors every bridgeless cubic graph.
We show that if true, this is a very exclusive situation.
Indeed, either ${\mathcal{H}}_{\mathcal{3}}\mathcal{=}\{\mathcal{P}\}$ or ${\mathcal{H}}_3$ is an infinite set and if
$r\ge 4$, then ${\mathcal{H}}_r$ is an infinite set. Similar results hold for the restriction on simple $r$-graphs. Moreover, we determine the set of smallest
$r$-graphs and show that it is a subset of ${\mathcal{H}}_r$.

This is joint work with Yulai Ma, Davide Mattiollo and Isaak H.~Wolf.