Can I read Good Acyclic Orientations of 4-Regular 4-Connected Graphs on EtoBox?

Good Acyclic Orientations of 4-Regular 4-Connected Graphs by Bang-Jensen, Joergen; Kriesell, Matthias is a scholarly article available to read on EtoBox.

What is Good Acyclic Orientations of 4-Regular 4-Connected Graphs about?

We study graphs which admit an acyclic orientation that contains an out-branching and in-branching which are arc-disjoint (such an orientation is called {\bf good}). A {\bf 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. Vertex-minimal 2T-graphs with at least two vertices, also known as {\bf generic circuits}, play an important role in rigidity theory for graphs. It was shown in \cite{bangGOpaper} that every generic circuit has a good orientation. Using this, several results on good orientations of 2T-graphs were obtained in \cite{bangGOpaper}. It is an open problem whether there exist a polynomial algorithm for deciding whether a given 2T-graph has a good orientation. In \cite{bangGOpaper} complex constructions of 2T-graphs with no good orientation were given, indicating that the problem might be very difficult. In this paper we focus on so-called {\bf 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 o

Author

Bang-Jensen, Joergen; Kriesell, Matthias

Published

2019

Language

EN