3 citations · 9 across the 10 of their papers we have counts for
14 papers
Exploration of graphs with excluded minors
Julia Baligacs, Yann Disser, Irene Heinrich +1
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and…
Twin-width of graphs with tree-structured decompositions
Irene Heinrich, Simon Raßmann
The twin-width of a graph measures its distance to co-graphs and generalizes classical width concepts such as tree-width or rank-width. Since its introduction in 2020 (Bonnet et. a…
Countable ultrahomogeneous graphs on two imprimitive color classes
Sofia Brenner, Irene Heinrich
We classify the countable ultrahomogeneous 2-vertex-colored graphs in which the color classes are imprimitive, i.e., up to complementation they form disjoint unions of cliques. Thi…
Line Planning in Public Transport: Bypassing Line Pool Generation
Irene Heinrich, Philine Schiewe, Constantin Seebach
Line planning, i.e. choosing paths which are operated by one vehicle end-to-end, is an important aspect of public transport planning. While there exists heuristic procedures for ge…
Reductions for the 3-Decomposition Conjecture
Oliver Bachtler, Irene Heinrich
The 3-decomposition conjecture is wide open. It asserts that every finite connected cubic graph can be decomposed into a spanning tree, a disjoint union of cycles, and a matching.…
Classification of Finite Highly Regular Vertex-Coloured Graphs
Irene Heinrich, Thomas Schneider, Pascal Schweitzer
A coloured graph is k-ultrahomogeneous if every isomorphism between two induced subgraphs of order at most k extends to an automorphism. A coloured graph is t-tuple regular if the…
Automated Testing and Interactive Construction of Unavoidable Sets for Graph Classes of Small Path-width
Oliver Bachtler, Irene Heinrich
We present an interactive framework that, given a membership test for a graph class and a number , finds and tests unavoidable sets for the class of graphs in $\ma…
2.5-Connectivity: Unique Components, Critical Graphs, and Applications
Irene Heinrich, Till Heller, Eva Schmidt +1
If a biconnected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every biconnected graph has a…
Cycle Decompositions and Constructive Characterizations
Irene Heinrich, Manuel Streicher
Decomposing an Eulerian graph into a minimum respectively maximum number of edge disjoint cycles is an NP-complete problem. We prove that an Eulerian graph decomposes into a unique…
Hajós' cycle conjecture for small graphs
Irene Heinrich, Marco V. Natale, Manuel Streicher
Hajós' conjecture states that an Eulerian graph of order n can be decomposed into at most (n-1)/2 edge-disjoint cycles. We describe preprocessing steps, heuristics and integer prog…
Cycle decompositions of pathwidth-6 graphs
Elke Fuchs, Laura Gellert, Irene Heinrich
Hajós conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most (n - 1)/2 cycles. The conjecture is only proved for graph classes in which every…
Minimum Cycle Decomposition: A Constructive Characterization for Graphs of Treewidth Two with Node Degrees Two and Four
Irene Heinrich, Sven O. Krumke
Substantial efforts have been made to compute or estimate the minimum number of cycles needed to partition the edges of an Eulerian graph. We give an equivalent characteriza…
Counting Dominating Sets of Graphs
Irene Heinrich, Peter Tittmann
Counting dominating sets in a graph is closely related to the neighborhood complex of . We exploit this relation to prove that the number of dominating sets of a grap…
Large Values of the Clustering Coefficient
Michael Gentner, Irene Heinrich, Simon Jäger +1
A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (Collective dynamics of `small-world' networks, Nature 393 (1998) 440-442), is t…