We show that for every cubic graph Gwith sufficiently large girth there exists a probability
distribution on edge‐cuts in Gsuch that each edge is in a randomly chosen cut with …

Given two graphs, a mapping between their edge‐sets is cycle‐continuous, if the preimage
of every cycle is a cycle. The motivation for this definition is Jaeger's conjecture that for every …

Tension-continuous (shortly TT) mappings are mappings between the edge sets of graphs.
They generalize graph homomorphisms. At the same time, tension-continuous mappings …

We consider mappings between edge sets of graphs that lift tensions to tensions. Such
mappings are called tension-continuous mappings (shortly TT mappings). The existence of …

We provide a primal-dual framework for randomized approximation algorithms utilizing
semidefinite programming (SDP) relaxations. Our framework pairs a continuum of APX …

A graph homomorphism is a function between the vertex set of two graphs which maps pairs
of adjacent vertices to pairs of adjacent vertices. Many graph parameters can be expressed …

An Approximability-related Parameter on Graphs – Properties and Applications∗ Page 1 Discrete
Mathematics and Theoretical Computer Science DMTCS vol. 17:1, 2015, 33–66 An …

A graph homomorphism is a vertex map which carries edges from a source graph to edges
in a target graph. We study the approximability properties of the Weighted Maximum H …

We give a (computer assisted) proof that the edges of every graph with maximum degree 3
and girth at least 17 may be 5‐colored (possibly improperly) so that the complement of each …

A graph homomorphism is a vertex map which carries edges from a source graph to edges
in a target graph. The instances of the Weighted Maximum H-Colourable Subgraph problem …