Publications of Prof. Dr. Matthias Kriesell

Publications of the Group

Anzahl der Treffer: 188
Erstellt: Sun, 26 Jun 2022 16:42:26 +0200 in 0.0845 sec


Hörsch, Florian;
Checking the admissibility of odd-vertex pairings is hard. - In: Discrete applied mathematics, Bd. 317 (2022), S. 42-48

Nash-Williams proved that every graph has a well-balanced orientation. A key ingredient in his proof is admissible odd-vertex pairings. We show that for two slightly different definitions of admissible odd-vertex pairings, deciding whether a given odd-vertex pairing is admissible is co-NP-complete. This resolves a question of Frank. We also show that deciding whether a given graph has an orientation that satisfies arbitrary local arc-connectivity requirements is NP-complete.



https://doi.org/10.1016/j.dam.2022.04.004
Bang-Jensen, Jørgen; Havet, Frederic; Kriesell, Matthias; Yeo, Anders;
Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties. - In: Journal of graph theory, ISSN 1097-0118, Bd. 99 (2022), 4, S. 615-636

https://doi.org/10.1002/jgt.22755
Kriesell, Matthias;
A note on uniquely 10-colorable graphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 98 (2021), 1, S. 24-26

Hadwiger conjectured that every graph of chromatic number k admits a clique minor of order k. Here we prove for k ≤ 10, that every graph of chromatic number k with a unique k-coloring (up to the color names) admits a clique minor of order k. The proof does not rely on the Four Color Theorem.



https://doi.org/10.1002/jgt.22679
Bang-Jensen, Jørgen; Bessy, Stéphane; Huang, Jing; Kriesell, Matthias;
Good orientations of unions of edge-disjoint spanning trees. - In: Journal of graph theory, ISSN 1097-0118, Bd. 96 (2021), 4, S. 594-618

In this paper, we exhibit connections between the following subjects: Tree packing in graphs and digraphs (both behave completely different), the rigidity matroid of a graph, Henneberg moves on trees, the conjectures of Thomassen and Matthews and Sumner, and (s,t)-orderings of digraphs. We do this by studying graphs which admit acyclic orientations that contain an out-branching and in-branching which are arc-disjoint (such an orientation is called good). A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. It is a well-known result due to Tutte and Nash-Williams, respectively, that every 4-edge-connected graph contains a spanning 2T-graph. Vertex-minimal 2T-graphs with at least two vertices which are known as generic circuits play an important role in rigidity theory for graphs. We prove that every generic circuit has a good orientation. Using this result we prove that if G is 2T-graph whose vertex set has a partition V1,V2, ,Vk so that each Vi induces a generic circuit Gi of G and the set of edges between different Gi's form a matching in G, then G has a good orientation. We also obtain a characterization for the case when the set of edges between different Gi's form a double tree, that is, if we contract each Gi to one vertex, and delete parallel edges we obtain a tree. All our proofs are constructive and imply polynomial algorithms for finding the desired good orderings and the pairs of arc-disjoint branchings which certify that the orderings are good. We identify a structure which can be used to certify that a given 2T-graph does not have a good orientation.



https://doi.org/10.1002/jgt.22633
Mohr, Samuel;
Rooted structures in graphs : a project on Hadwiger's conjecture, rooted minors, and Tutte cycles. - Ilmenau : Universitätsbibliothek, 2020. - 1 Online-Ressource (viii, 131 Blätter)
Technische Universität Ilmenau, Dissertation 2020

Hadwigers Vermutung ist eine der anspruchsvollsten Vermutungen für Graphentheoretiker und bietet eine weitreichende Verallgemeinerung des Vierfarbensatzes. Ausgehend von dieser offenen Frage der strukturellen Graphentheorie werden gewurzelte Strukturen in Graphen diskutiert. Eine Transversale einer Partition ist definiert als eine Menge, welche genau ein Element aus jeder Menge der Partition enthält und sonst nichts. Für einen Graphen G und eine Teilmenge T seiner Knotenmenge ist ein gewurzelter Minor von G ein Minor, der T als Transversale seiner Taschen enthält. Sei T eine Transversale einer Färbung eines Graphen, sodass es ein System von kanten-disjunkten Wegen zwischen allen Knoten aus T gibt; dann stellt sich die Frage, ob es möglich ist, die Existenz eines vollständigen, in T gewurzelten Minors zu gewährleisten. Diese Frage ist eng mit Hadwigers Vermutung verwoben: Eine positive Antwort würde Hadwigers Vermutung für eindeutig färbbare Graphen bestätigen. In dieser Arbeit wird ebendiese Fragestellung untersucht sowie weitere Konzepte vorgestellt, welche bekannte Ideen der strukturellen Graphentheorie um eine Verwurzelung erweitern. Beispielsweise wird diskutiert, inwiefern hoch zusammenhängende Teilmengen der Knotenmenge einen hoch zusammenhängenden, gewurzelten Minor erzwingen. Zudem werden verschiedene Ideen von Hamiltonizität in planaren und nicht-planaren Graphen behandelt.



https://nbn-resolving.org/urn:nbn:de:gbv:ilm1-2020000294
Kriesell, Matthias;
Maximal ambiguously k-colorable graphs. - In: Journal of combinatorial theory, Bd. 140 (2020), S. 248-262

https://doi.org/10.1016/j.jctb.2019.05.007
Kriesell, Matthias; Mohr, Samuel;
Rooted complete minors in line graphs with a Kempe coloring. - In: Graphs and combinatorics, ISSN 1435-5914, Bd. 35 (2019), 2, S. 551-557

https://doi.org/10.1007/s00373-019-02012-7
Kriesell, Matthias;
Nonseparating K4-subdivisions in graphs of minimum degree at least 4. - In: Journal of graph theory, ISSN 1097-0118, Bd. 89 (2018), 2, S. 194-213
Im Titel ist "4" tiefgestellt

https://doi.org/10.1002/jgt.22247
Kriesell, Matthias; Schmidt, Jens M.;
More on foxes. - In: Journal of graph theory, ISSN 1097-0118, Bd. 89 (2018), 2, S. 101-114

https://doi.org/10.1002/jgt.22243
Brause, Christoph; Kemnitz, Arnfried; Marangio, Massimiliano; Pruchnewski, Anja; Voigt, Margit;
Sum choice number of generalized [theta]-graphs. - In: Discrete mathematics, Bd. 340 (2017), 11, S. 2633-2640

https://doi.org/10.1016/j.disc.2016.11.028