Rooted minors and locally spanning subgraphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 105 (2024), 2, S. 209-229
Results on the existence of various types of spanning subgraphs of graphs are milestones in structural graph theory and have been diversified in several directions. In the present paper, we consider “local” versions of such statements. In 1966, for instance, D. W. Barnette proved that a 3-connected planar graph contains a spanning tree of maximum degree at most 3. A local translation of this statement is that if G is a planar graph, X is a subset of specified vertices of G such that X cannot be separated in G by removing two or fewer vertices of G, then G has a tree of maximum degree at most 3 containing all vertices of X. Our results constitute a general machinery for strengthening statements about k-connected graphs (for 1 ≤ k ≤ 4) to locally spanning versions, that is, subgraphs containing a set X ⊆ V (G) of a (not necessarily planar) graph G in which only X has high connectedness. Given a graph G and X ⊆ V (G), we say M is a minor of G rooted at X, if M is a minor of G such that each bag of M contains at most one vertex of X and X is a subset of the union of all bags. We show that G has a highly connected minor rooted at X if X ⊆ V (G) cannot be separated in G by removing a few vertices of G. Combining these investigations and the theory of Tutte paths in the planar case yields locally spanning versions of six well-known results about degree-bounded trees, Hamiltonian paths and cycles, and 2-connected subgraphs of graphs.
https://doi.org/10.1002/jgt.23012
Complexity of (arc)-connectivity problems involving arc-reversals or deorientations. - In: Theoretical computer science, Bd. 973 (2023), 114097
By a well known theorem of Robbins, a graph G has a strongly connected orientation if and only if G is 2-edge-connected and it is easy to find, in linear time, either a cut edge of G or a strong orientation of G. A result of Durand de Gevigney shows that for every it is NP-hard to decide if a given graph G has a k-strong orientation. Thomassen showed that one can check in polynomial time whether a given graph has a 2-strong orientation. This implies that for a given digraph D we can determine in polynomial time whether we can reorient (=reverse) some arcs of to obtain a 2-strong digraph. This naturally leads to the question of determining the minimum number of such arcs to reverse before the resulting graph is 2-strong. In this paper we show that finding this number is NP-hard. If a 2-connected graph G has no 2-strong orientation, we may ask how many of its edges we may orient so that the resulting mixed graph is still 2-strong. Similarly, we may ask for a 2-edge-connected graph G how many of its edges we can orient such that the resulting mixed graph remains 2-arc-strong. We prove that when restricted to graphs satisfying suitable connectivity conditions, both of these problems are equivalent to finding the minimum number of edges we must double in a 2-edge-connected graph in order to obtain a 4-edge-connected graph. Using this, we show that all these three problems are NP-hard. Finally, we consider the operation of deorienting an arc uv of a digraph D meaning replacing it by an undirected edge between the same vertices. In terms of connectivity properties, this is equivalent to adding the opposite arc vu to D. We prove that for every it is NP-hard to find the minimum number of arcs to deorient in a digraph D in order to obtain an ℓ-strong digraph.
https://doi.org/10.1016/j.tcs.2023.114097
Contractible edges in longest cycles. - In: Journal of graph theory, ISSN 1097-0118, Bd. 103 (2023), 3, S. 542-563
https://doi.org/10.1002/jgt.22935
Globally balancing spanning trees. - In: European journal of combinatorics, Bd. 109 (2023), 103644
https://doi.org/10.1016/j.ejc.2022.103644
On the complexity of finding well-balanced orientations with upper bounds on the out-degrees. - In: Journal of combinatorial optimization, ISSN 1573-2886, Bd. 45 (2023), 1, 30, S. 1-14
https://doi.org/10.1007/s10878-022-00962-y
Reachability in arborescence packings. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 320 (2022), S. 170-183
Fortier et al. proposed several research problems on packing arborescences and settled some of them. Others were later solved by Matsuoka and Tanigawa and by Gao and Yang. The last open problem is settled in this article. We show how to turn an inductive idea used in the latter two articles into a simple proof technique that allows to relate previous results on arborescence packings. We prove that a strong version of Edmonds’ theorem on packing spanning arborescences implies Kamiyama, Katoh and Takizawa’s result on packing reachability arborescences and that Durand de Gevigney, Nguyen and Szigeti’s theorem on matroid-based packing of arborescences implies Király’s result on matroid-reachability-based packing of arborescences. Further, we deduce a new result on matroid-reachability-based packing of mixed hyperarborescences from a theorem on matroid-based packing of mixed hyperarborescences due to Fortier et al.. Finally, we deal with the algorithmic aspects of the problems considered. We first obtain algorithms to find the desired packings of arborescences in all settings and then apply Edmonds’ weighted matroid intersection algorithm to also find solutions minimizing a given weight function.
https://doi.org/10.1016/j.dam.2022.05.018
Good acyclic orientations of 4-regular 4-connected graphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 100 (2022), 4, S. 698-720
An st-ordering of a graph G=(V,E) is an ordering v1,v2,…,vn of its vertex set such that s=v1,t=vn and every vertex vi with i=2,3,…,n-1 has both a lower numbered and a higher numbered neighbor. Such orderings have played an important role in algorithms for planarity testing. It is well-known that every 2-connected graph has an st-ordering for every choice of distinct vertices s,t. An st-ordering of a graph G corresponds directly to a so-called bipolar orientation of G, that is, an acyclic orientation D of G in which s is the unique source and t is the unique sink. Clearly every bipolar orientation of a graph has an out-branching rooted at the source vertex and an in-branching rooted at the sink vertex. In this paper, we study graphs which admit a bipolar orientation that contains 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. Clearly a graph has a good orientation if and only if it contains a spanning 2T-graph with a good orientation, implying that 2T-graphs play a central role. 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, also known as generic circuits, play an important role in rigidity theory for graphs. Recently with Bessy and Huang we proved that every generic circuit has a good orientation. In fact, we may specify the roots of the two branchings arbitrarily as long as they are distinct. Using this, several results on good orientations of 2T-graphs were obtained. It is an open problem whether there exists a polynomial algorithm for deciding whether a given 2T-graph has a good orientation. Complex constructions of 2T-graphs with no good orientation were given in work by Bang-Jensen, Bessy, Huang and Kriesell (2021) indicating that the problem might be very difficult. In this paper, we focus on so-called quartics which are 2T-graphs where every vertex has degree 3 or 4. We identify a sufficient condition for a quartic to have a good orientation, give a polynomial algorithm to recognize quartics satisfying the condition and a polynomial algorithm to produce a good orientation when this condition is met. As a consequence of these results we prove that every 4-regular and 4-connected graph has a good orientation, where, as for generic circuits, we may specify the roots of the two branchings arbitrarily as long as they are distinct. We also provide evidence that even for quartics it may be difficult to find a characterization of those instances which have a good orientation. We also show that every graph on n≥8 vertices and of minimum degree at least has a good orientation. Finally we pose a number of open problems.
https://doi.org/10.1002/jgt.22803
Checking the admissibility of odd-vertex pairings is hard. - In: Discrete applied mathematics, ISSN 1872-6771, 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
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
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