Packing A-Paths of Length Zero Modulo Four
We show that A-paths of length 0 modulo 4 have the Erdős-Pósa property. We also prove that A-paths of length 2 modulo 4 have the property but that A-paths of length 1 or of length 3 modulo 4 do not have it.
Source author record
Henning Bruhn
Henning Bruhn appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
19works
5topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
19 published item(s)
preprint2016arXiv
$t$-perfection in $P_5$-free graphs
A graph is called $t$-perfect if its stable set polytope is fully described by non-negativity, edge and odd-cycle constraints. We characterise $P_5$-free $t$-perfect graphs in terms of forbidden $t$-minors. Moreover, we show that $P_5$-free $t$-perfect graphs can always be coloured with three colours, and that they can be recognised in polynomial time.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
$h$-perfect plane triangulations
We characterise $t$-perfect plane triangulations by forbidden induced subgraphs. As a consequence, we obtain that a plane triangulation is $h$-perfect if and only if it is perfect.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
A stronger bound for the strong chromatic index
We prove $χ_s'(G)\leq 1.93 Δ(G)^2$ for graphs of sufficiently large maximum degree where $χ_s'(G)$ is the strong chromatic index of $G$. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where it is allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Jacobsthal numbers in generalised Petersen graphs
We prove that the number of $1$-factorisations of a generalised Petersen graph of the type $GP(3k,k)$ is equal to the $k$th Jacobsthal number $J(k)$ if $k$ is odd, and equal to $4J(k)$, when $k$ is even. Moreover, we verify the list colouring conjecture for $GP(3k,k)$.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Long cycles through prescribed vertices have the Erdős-Pósa property
We prove that for every graph, any vertex subset $S$, and given integers $k,\ell$: there are $k$ disjoint cycles of length at least $\ell$ that each contain at least one vertex from $S$, or a vertex set of size $O(\ell \cdot k \log k)$ that meets all such cycles. This generalises previous results of Fiorini and Hendrickx and of Pontecorvi and Wollan. In addition, we describe an algorithm for our main result that runs in $O(k \log k \cdot s^2 \cdot (f(\ell) \cdot n+m))$ time, where $s$ denotes the cardinality of $S$.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Structural parameterizations for boxicity
The boxicity of a graph $G$ is the least integer $d$ such that $G$ has an intersection model of axis-aligned $d$-dimensional boxes. Boxicity, the problem of deciding whether a given graph $G$ has boxicity at most $d$, is NP-complete for every fixed $d \ge 2$. We show that boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al., that boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that boxicity admits an additive $1$-approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of Adiga et al. that boxicity remains NP-complete when parameterized by the treewidth.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Axioms for infinite matroids
We give axiomatic foundations for non-finitary infinite matroids with duality, in terms of independent sets, bases, circuits, closure and rank. This completes the solution to a problem of Rado of 1966.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Claw-free t-perfect graphs can be recognised in polynomial time
A graph is called t-perfect if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We show that it can be decided in polynomial time whether a given claw-free graph is t-perfect.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
List edge-colouring and total colouring in graphs of low treewidth
We prove that the list chromatic index of a graph of maximum degree $Δ$ and treewidth $\leq \sqrt{2Δ} -3$ is $Δ$; and that the total chromatic number of a graph of maximum degree $Δ$ and treewidth $\leq Δ/3 +1$ is $Δ+1$. This improves results by Meeks and Scott.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
The graph formulation of the union-closed sets conjecture
In 1979 Frankl conjectured that in a finite non-trivial union-closed collection of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
The journey of the union-closed sets conjecture
We survey the state of the union-closed sets conjecture.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
The union-closed sets conjecture almost holds for almost all random bipartite graphs
Frankl's union-closed sets conjecture states that in every finite union-closed set of sets, there is an element that is contained in at least half of the member-sets (provided there are at least two members). The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets. We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl's conjecture.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Infinite matroids in graphs
It has recently been shown that infinite matroids can be axiomatized in a way that is very similar to finite matroids and permits duality. This was previously thought impossible, since finitary infinite matroids must have non-finitary duals. In this paper we illustrate the new theory by exhibiting its implications for the cycle and bond matroids of infinite graphs. We also describe their algebraic cycle matroids, those whose circuits are the finite cycles and double rays, and determine their duals. Finally, we give a sufficient condition for a matroid to be representable in a sense adapted to infinite matroids. Which graphic matroids are representable in this sense remains an open question.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Matroid and Tutte-connectivity in infinite graphs
We relate matroid connectivity to Tutte-connectivity in an infinite graph. Moreover, we show that the two cycle matroids, the finite-cycle matroid and the cycle matroid, in which also infinite cycles are taken into account, have the same connectivity function. As an application we re-prove that, also for infinite graphs, Tutte-connectivity is invariant under taking dual graphs.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Minimal bricks have many vertices of small degree
We prove that every minimal brick on n vertices has at least n/9 vertices of degree at most 4.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Colouring stability two unit disk graphs
We prove that every stability two unit disk graph has chromatic number at most 3/2 times its clique number.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Finite connectivity in infinite matroids
We introduce a connectivity function for infinite matroids with properties similar to the connectivity function of a finite matroid, such as submodularity and invariance under duality. As an application we use it to extend Tutte's linking theorem to finitary and to co-finitary matroids.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Theoretical description of spherically confined strongly correlated Yukawa plasmas
A theoretical description of the radial density profile for charged particles with Yukawa interaction in a harmonic trap is described. At strong Coulomb coupling shell structure is observed in both computer simulations and experiments. Correlations responsible for such shell structure are described here using a recently developed model based in density functional theory. A wide range of particle number, Coulomb coupling, and screening lengths is considered within the fluid phase. A hypernetted chain approximation shows the formation of shell structure, but fails to give quantitative agreement with Monte Carlo simulation results at strong coupling. Significantly better agreement is obtained within the hypernetted chain structure using a renormalized coupling constant, representing bridge function corrections.
0 citations0 reviewsNo code linkedOpen access