The orientation number of a graph G , denoted by o ( G ) , is the minimum integer k such that there exists an orientation D with d D + ( v ) ≤ k for every v ∈ V ( G ) , where d D + ( v ) is the out-degree of v in the directed graph G with respect to the orientation D . In this paper, we define its list-analog as the list-orientation number o ℓ ( G ) , and conjecture that o ℓ ( G ) ≤ o ( G ) + 2 for every graph G . We give partial solutions and tight constructions for this conjecture for some fundamental classes of graphs, such as bipartite graphs, graphs with o ( G ) ≤ 2 , and planar graphs. In addition, we extend some of the results from unsigned graphs to signed ones.

In this article, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths \(\mathcal{P}\) and \(\mathcal{Q}\) connecting the same set of terminal pairs, we aim to determine whether \(\mathcal{P}\) can be transformed to \(\mathcal{Q}\) by repeatedly replacing one path with another path so that the intermediates are also k disjoint paths. The problem is called Disjoint Paths Reconfiguration . We first show that Disjoint Paths Reconfiguration is \(\mathsf{PSPACE}\) -complete even when \(k=2\) . On the other hand, we prove that, when the graph is embedded on a plane and all paths in \(\mathcal{P}\) and \(\mathcal{Q}\) connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint s - t paths as a variant. We show that the disjoint s - t paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is \(\mathsf{PSPACE}\) -complete in general.

In this paper, we consider a transformation of $k$ disjoint paths in a graph. For a graph and a pair of $k$ disjoint paths $\mathcal{P}$ and $\mathcal{Q}$ connecting the same set of terminal pairs, we aim to determine whether $\mathcal{P}$ can be transformed to $\mathcal{Q}$ by repeatedly replacing one path with another path so that the intermediates are also $k$ disjoint paths. The problem is called Disjoint Paths Reconfiguration. We first show that Disjoint Paths Reconfiguration is PSPACE-complete even when $k=2$. On the other hand, we prove that, when the graph is embedded on a plane and all paths in $\mathcal{P}$ and $\mathcal{Q}$ connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint $s$-$t$ paths as a variant. We show that the disjoint $s$-$t$ paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.

We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k -edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge connectivity, and the final orientation is k -edge connected. This yields an “edge-flip based” new proof of Nash-Williams’ theorem: A undirected graph G has a k -edge-connected orientation if and only if G is 2k -edge connected. As another consequence of the theorem, we prove that the edge-flip graph of k -edge-connected orientations of an undirected graph G is connected if G is (2k+2) -edge connected. This has been known to be true only when k=1 .

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

We initiate the study of k-edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k-edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k-edge-connected. This yields an “edge-flip based” new proof of Nash-Williams' theorem: an undirected graph G has a k-edge-connected orientation if and only if G is 2k-edge-connected. As another consequence of the theorem, we prove that the edge-flip graph of k-edge-connected orientations of an undirected graph G is connected if G is (2k + 2)-edge-connected. This has been known to be true only when k = 1.

In order to attack some problems in computational geometry, Hoffmann and Kriegel [ SIAM J. Discrete Math., 9 (1996), pp. 210--224] considered the problem of whether a plane map can be extended to a 3-colorable triangulation by adding edges. In this paper, we improve their results to maps on nonspherical surfaces, by showing the following two results for a mosaic, that is, a map on a surface each of whose faces is triangular or quadrangular: a necessary and sufficient condition for mosaics on a surface to be extended to a 3-colorable triangulation (Theorem 5) and an explicit formula for calculating the number of distinct 3-colorable triangulations extended from a given mosaic on a surface (Theorem 6). These results suggest a significant gap between the planar case and the nonspherical case. We also show that they improve several known results and have an application to a polychromatic coloring.

For a positive integer $k$, a book (with $k$ pages) is a topological space consisting of a spine, which is a line, and $k$ pages, which are half-planes with the spine as their boundary. We say that a graph $G$ admits a $k$-page book embedding or is $k$-page book embeddable if there exists a linear ordering of the vertices on the spine and one can assign the edges of $G$ to $k$ pages such that no two edges of the same page cross. Yannakakis proved that every plane graph admits a 4-page book embedding. In this paper, we improve this to graphs on the projective plane, that is, those embedded on the projective plane without edge-crossings. Nakamoto and Nozawa showed that every graph on the projective plane admits a 9-page book embedding. In this paper, we improve the latter result to 6-page embedding. Furthermore, we also prove that every graph on the projective plane admits a 3-page book embedding if it is 5-connected and a 5-page book embedding if it is 4-connected. Our idea of the proofs is to use a Tutte path, which is different from previous ones.

A seminal theorem of Tutte states that 4-connected planar graphs are Hamiltonian. Applying a result of Thomas and Yu, one can show that every 4-connected graph with crossing number 1 is Hamiltonian. In this paper, we continue along this path and prove the titular statement. We also discuss the traceability and Hamiltonicity of 3-connected graphs with small crossing number and few 3-cuts, and present applications of our results.

It is known that a 3-edge-connected graph has a spanning even subgraph in which every component contains at least five vertices, and the lower bound is best possible. A natural question arises of whether we can improve the lower bound by changing the spanning property with the dominating property. In this paper, we show that a 3-edge-connected cubic graph has a dominating even subgraph in which every component contains at least six vertices.

A Halin graph is a plane graph constructed from a planar drawing of a tree by connecting all leaves of the tree with a cycle which passes around the boundary of the graph. The tree must have four or more vertices and no vertices of degree two. Halin graphs have many nice properties such as being Hamiltonian and remaining Hamiltonian after any single vertex deletion. In 1975, Lovász and Plummer conjectured that every 4-connected plane triangulation contains a spanning Halin subgraph. We recently gave a negative answer to this conjecture. In this paper, we construct an infinite class of 5-connected plane triangulations without a spanning Halin subgraph. Our smallest example contains 512 vertices.

We provide a complete structural characterization of $K_{2,4}$-minor-free graphs. The 3-connected $K_{2,4}$-minor-free graphs consist of nine small graphs on at most eight vertices, together with a family of planar graphs that contains $2n-8$ nonisomorphic graphs of order $n$ for each $n \geq 5$ as well as $K_4$. To describe the 2-connected $K_{2,4}$-minor-free graphs we use $xy$-outerplanar graphs, graphs embeddable in the plane with a Hamilton $xy$-path so that all other edges lie on one side of this path. We show that, subject to an appropriate connectivity condition, $xy$-outerplanar graphs are precisely the graphs that have no rooted $K_{2,2}$ minor where $x$ and $y$ correspond to the two vertices on one side of the bipartition of $K_{2,2}$. Each 2-connected $K_{2,4}$-minor-free graph is then (i) outerplanar, (ii) the union of three $xy$-outerplanar graphs and possibly the edge $xy$, or (iii) obtained from a 3-connected $K_{2,4}$-minor-free graph by replacing each edge $x_iy_i$ in a set $\{x_1 y_1, x_2 y_2, \ldots, x_k y_k\}$ satisfying a certain condition by an $x_i y_i$-outerplanar graph. From our characterization it follows that a $K_{2,4}$-minor-free graph has a Hamilton cycle if it is 3-connected and a Hamilton path if it is 2-connected. Also, every 2-connected $K_{2,4}$-minor-free graph is either planar or else toroidal and projective-planar.

The problem on the Hamiltonicity of graphs is well studied in discrete algorithm and graph theory because of its relation to the traveling salesman problem. Starting with Tutte's result, stating that every 4-connected planar graph is Hamiltonian, several researchers have studied the Hamiltonicity of graphs on surfaces. Extending Tutte's technique, Thomassen proved that every 4-connected planar graph is in fact Hamiltonian-connected, i.e., there is a Hamiltonian path connecting any two prescribed vertices. For graphs on the torus, Thomas and Yu showed that every 5-connected graph on the torus has a Hamiltonian cycle. In this paper, we prove the following result which generalizes Thomas and Yu's result. Every 5-connected graph on the torus is Hamiltonian-connected. Our result is best possible in the sense that we cannot lower the connectivity 5 (i.e., there is a 4-connected graph on the torus which is not Hamiltonian-connected). Moreover, our proof is constructive in a sense that it gives rise to a polynomial time (indeed $O(n^2)$-time) algorithm to construct a Hamiltonian path between any two specified vertices, if an input graph is a 5-connected graph on the torus.

In 1986, Thomassen posed the following conjecture: every 4-connected line graph has a Hamiltonian cycle. As a possible approach to the conjecture, many researchers have considered statements that are equivalent or related to it. One of them is the conjecture by Bondy: there exists a constant $c_0$ with $0 < c_0 \leq 1$ such that every cyclically 4-edge-connected cubic graph $H$ has a cycle of length at least $c_0 |V(H)|$. It is known that Thomassen's conjecture implies Bondy's conjecture, but nothing about the converse has been shown. In this paper, we show that Bondy's conjecture implies a slightly weaker version of Thomassen's conjecture: every 4-connected line graph with minimum degree at least 5 has a Hamiltonian cycle.

A \sl Halin graph is a simple plane graph consisting of a tree without degree 2 vertices and a cycle induced by the leaves of the tree. In 1975, Lovász and Plummer conjectured that every 4-connected plane triangulation has a spanning Halin subgraph. In this paper, we construct an infinite family of counterexamples to the conjecture.

Extension of a graph $G$ is the construction of a new graph with certain properties by adding edges to some pairs of vertices in $G$. In this paper, we focus on extension of a quadrangulation of a surface to even triangulations, where a quadrangulation is a map on a surface with every face quadrangular and a triangulation is even if all the vertices have even degree. Zhang and He [SIAM J. Comput., 34 (2005), pp. 683--696] gave a formula for the exact number of distinct even triangulations extended from a given plane quadrangulation, and a lower bound of the number for the case of orientable nonspherical surfaces. They also posed the problem of finding the exact number for the latter case. In this paper, using topological methods, we improve the results by Zhang and He in the following directions: (I) extension of quadrangulations of a nonorientable surface and (II) complete enumeration of even triangulations extended from a given quadrangulation of a nonspherical surface. Indeed, we completely solve the problem by Zhang and He.

We generalize the following two seminal results. 1. Thomassen's result [19] in 1983, which says that every 4-connected planar graph is hamiltonian-connected (which generalizes the old result of Tutte [20] in 1956, which says that every 4-connected planar graph is hamiltonian). 2. Thomas and Yu's result [16] in 1994, which says that every 4-connected projective planar graph is hamiltonian. Here, hamiltonian-connected means that for any two vertices u, v, there is a hamiltonian path between u and v (and hence this generalizes the existence of hamiltonian cycles). Specifically, we prove the following; Every 4-connected projective planar graph is hamiltonian-connected. This proves a conjecture of Dean [3] in 1990. Our result is best possible in many senses. First, we cannot lower the connectivity 4. Secondly, we cannot generalize our result to a surface with higher genus (i.e, there is a 4-connected graph on the torus which is not hamiltonian-connected). Our proof is constructive in the sense that there is a polynomial time (in fact, O(n2) time) algorithm to find, given two vertices in a 4-connected projective planar graph, a hamiltonian path between these two vertices.

For a subset $A$ of the set of positive integers, a graph $G$ is called $A$-coverable if $G$ has a cycle (a subgraph in which all vertices have even degree) which intersects all edge-cuts $T$ in $G$ with $|T| \in A$, and $A$ is said to be coverable if all graphs are $A$-coverable. As a possible approach to the dominating cycle conjecture, Kaiser and Škrekovski conjectured in [SIAM J. Discrete Math., 22 (2008), pp. 861--874] that $\mathbb{N} +3$ is coverable, where $\mathbb{N} +3 = \{4,5,6, \ldots\}$. In this paper, we disprove Kaiser and Škrekovski's conjecture by showing that there exist infinitely many graphs which are not $\{4,5\}$-coverable.

For a spanning tree $T$ of a graph $G$, we define the total excess $te(T,k)$ of $T$ from $k$ as $te(T,k) := \sum_{v \in V(T)} \max \{d_T(v)-k, 0\}$, where $d_T(v)$ is the degree of a vertex $v$ in $T$. In this paper, we show the following: if $G$ is a $3$-connected graph on a surface with Euler characteristic $\chi < 0$, then $G$ has a spanning $\lceil\frac{8-2\chi}{3}\rceil$-tree $T$ with $te(T, 3) \leq -2\chi-1$. We also show an application of this theorem to finding “light” connected subgraphs in a $3$-connected graph on a surface.

We consider the following problem which is motivated by two different contexts independently, namely graph theory and combinatorial optimization. Given a 3-connected planar graph G with n vertices, is there a spanning closed walk W with at most 4n/3 edges? In graph theory, the above question is motivated by the famous hamiltonian result by Tutte in 1956 which says that every 4-connected planar graph is hamiltonian (a simpler proof is given by Thomassen in 1983). What happens if we relax the 4-connectivity? There is a 3-connected planar graph that is not hamiltonian, but how about a spanning close walk (which is exactly a traveling salesman tour. Sometimes such a walk is called hamiltonian walk)? How many edges are necessary to cover all the vertices of a 3-connected planar graph by a closed walk? This is exactly the above question. In combinatorial optimization, the famous traveling salesman problem in metric graphs is one of most fundamental NP-hard optimization problems. In spite of a vast amount of research several important questions remain open. In particular, the best known upper bound is not believed to be best possible. A promising direction to improve this approximation guarantee, has long been to understand the power of a linear program known as the Held-Karp relaxation [11]. On the one hand, the best lower bound on its integrality gap (for the symmetric case) is 4/3 and indeed the famous (so called 4/3-)conjecture said that this lower bound would be tight [10]. Goemans pointed out that there is a planar graph that achieves this bound. So he brought attention to the above question, i.e, the famous 4/3-conjecture is always true for 3-connected planar graphs. We prove the above problem in the following strong form; Given a circuit graph (which is obtained from a 3-connected planar graph by deleting one vertex) with n vertices, there is a spanning closed walk with at most 4(n − 1)/3 edges such that each edge is used at most twice. Moreover, our proof is constructive (and purely combinatorial) in a sense that there is an O(n2) algorithm to construct, given a 3-connected planar graph, such a walk. We shall construct an example that shows that the bound 4(n − 1)/3 is essentially tight. We also point out that 2-connected planar graphs may not have such a walk, as K2,n − 2 shows.

Endo proved that every toroidal graph has a book embedding with at most seven pages. In this paper, we prove that every toroidal bipartite graph has a book embedding with at most five pages. In order to do so, we prove that every bipartite torus quadrangulation Q with n vertices admits two disjoint noncontractible simple closed curves cutting the torus into two annuli so that each of the two annuli contains a spanning connected subgraph of Q with exactly n edges satisfying a certain condition.