Vertex-disjoint paths and edge-disjoint branchings in directed graphs

A theorem of J. Edmonds states that a directed graph has k edge-disjoint branchings rooted at a vertex r if and only if every vertex has k edge-disjoint paths to r. We conjecture an extension of this theorem to vertex-disjoint paths and give a constructive proof of the conjecture in the case k = 2.     

On tree‐decompositions of one‐ended graphs

A graph is one‐ended if it contains a ray (a one way infinite path) and whenever we remove a finite number of vertices from the graph then what remains has only one component which contains rays. A vertex v dominates a ray in the end if there are infinitely many paths connecting v to the ray such that any two of these paths have only the vertex v in common. We prove that if a one‐ended graph contains no ray which is dominated by a vertex and no infinite family of pairwise disjoint rays, then it has a tree‐decomposition such that the decomposition tree is one‐ended and the tree‐decomposition is invariant under the group of automorphisms. This can be applied to prove a conjecture of Halin from 2000 that the automorphism group of such a graph cannot be countably infinite and solves a recent problem of Boutin and Imrich. Furthermore, it implies that every transitive one‐ended graph contains an infinite family of pairwise disjoint rays.     

A unified approach to known and unknown cases of Berge's conjecture

Berge's elegant dipath partition conjecture from 1982 states that in a dipath partition P of the vertex set of a digraph minimizing , there exists a collection C^k of k disjoint independent sets, where each dipath P∈P meets exactly min{|P|, k} of the independent sets in C. This conjecture extends Linial's conjecture, the Greene–Kleitman Theorem and Dilworth's Theorem for all digraphs. The conjecture is known to be true for acyclic digraphs. For general digraphs, it is known for k=1 by the Gallai–Milgram Theorem, for k?λ (where λis the number of vertices in the longest dipath in the graph), by the Gallai–Roy Theorem, and when the optimal path partition P contains only dipaths P with |P|?k. Recently, it was proved (Eur J Combin (2007)) for k=2. There was no proof that covers all the known cases of Berge's conjecture. In this article, we give an algorithmic proof of a stronger version of the conjecture for acyclic digraphs, using network flows, which covers all the known cases, except the case k=2, and the new, unknown case, of k=λ?1 for all digraphs. So far, there has been no proof that unified all these cases. This proof gives hope for finding a proof for all k.     

Path decompositions of multigraphs

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and μ(x) respectively. Define Ø(x) = the least even integer ≥ μ(x), if d(x) is even, the least odd integer ≥ μ(x), if d(x) is odd. In this paper it is shown that every multigraph G admits a faithful path decomposition—a partition P of the edges of G into simple paths such that every vertex x of G is an end of exactly Ø(x) paths in P. This result generalizes Lovász's path decomposition theorem, Li's perfect path double cover theorem (conjectured by Bondy), and a result of Fan concerning path covers of weighted graphs. It also implies an upper bound on the number of paths in a minimum path decomposition of a multigraph, which motivates a generalization of Gallai's path decomposition conjecture. © 1995 John Wiley & Sons, Inc.     

Claw‐decompositions and tutte‐orientations

We conjecture that, for each tree T, there exists a natural number k_T such that the following holds: If G is a k_T‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K_1,3 (the claw), this holds if and only if there exists a (smallest) natural number k_t such that every k_t‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that k_t = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006     

Vertex pancyclic in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. The topic of this paper is to investigate vertex k‐pancyclicity of in‐tournaments of order n, where for some 3 ≤ k ≤ n, every vertex belongs to a cycle of length p for every k ≤ p ≤ n. We give sharp lower bounds for the minimum degree such that a strong in‐tournament is vertex k‐pancyclic for k ≤ 5 and k ≥ n − 3. In the latter case, we even show that the in‐tournaments in consideration are fully (n − 3)‐extendable which means that every vertex belongs to a cycle of length n − 3 and that the vertex set of every cycle of length at least n − 3 is contained in a cycle of length one greater. In accordance with these results, we state the conjecture that every strong in‐tournament of order n with minimum degree greater than is vertex k‐pancyclic for 5 < k < n − 3, and we present a family of examples showing that this bound would be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 84–104, 2001     

Graph decomposition with applications to subdivisions and path systems modulo k

The existence of a function α(k) (where k is a natural number) is established such that the vertex set of any graph G of minimum degree at least α(k) has a decomposition A ∪ B ∪ C such that G(A) has minimum degree at least k, each vertex of A is joined to at least k vertices of B, and no two vertices of B are separated by fewer than k vertices in G(G ∪ C). This is applied to prove the existence of subdivisions of complete bipartite graphs (complete graphs) with prescribed path lengths modulo k in graphs of sufficiently high minimum degree (chromatic number) and path systems with prescribed ends and prescribed lengths modulo k in graphs of sufficiently high connectivity.     

The gallai-younger conjecture for planar graphs

Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG–X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs.     

Kings in locally semicomplete digraphs

A k‐king in a digraph D is a vertex which can reach every other vertex by a directed path of length at most k. We consider k‐kings in locally semicomplete digraphs and mainly prove that all strong locally semicomplete digraphs which are not round decomposable contain a 2‐king. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 279–287, 2010     

Graphs whose choice number is equal to their chromatic number

A graph G is k-choosable if it admits a vertex-coloring whenever the colors allowed at each vertex are restricted to a list of length k. If χ denotes the usual chromatic number of G, we are interested in which kind of G is χ-choosable. This question contains a famous conjecture, which states that every line-graph is χ-choosable. We present some other classes of graphs that are χ-choosable; all these classes are related to claw-free graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 87–97, 1998     

Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs.     

Multiple cover time

Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within a constant factor of the number of times predicted by the stationary distribution. Thus the blanket time is, essentially, the number of steps required of a random walk in order that the observed distribution reflect the stationary distribution. We provide substantial evidence for the following conjecture: that the blanket time of a graph never exceeds the cover time by more than a constant factor. In other words, at the cost of a multiplicative constant one can hit every vertex often instead of merely once. We prove the conjecture in the case where the cover time and maximum hitting time differ by a logarithmic factor. This case includes almost all graphs, as well as most “natural” graphs: the hypercube, k-dimensional lattices for k ≥ 2, balanced k-ary trees, and expanders. We further prove the conjecture for perhaps the most natural graphs not falling in the above case: paths and cycles. Finally, we prove the conjecture in the case of independent stochastic processes. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 403–411 (1996)     

Counterexamples to faudree and schelp's conjecture on hamiltonian-connected graphs

Faudree and Schelp conjectured that for any two vertices x, y in a Hamiltonian-connected graph G and for any integer k, where n/2 ? k ? n ? 1, G has a path of length k connecting x and y. However, we show in this paper that there are infinitely many exceptions to this conjecture and we comment on some problems on path length distribution raised by Faudree and Schelp.     

A Local Property of Large Polyhedral Maps on Compact 2-Dimensional Manifolds

We prove that each polyhedral map G on a compact 2-manifold, which has large enough vertices, contains a k-path, a path on k vertices, such that each vertex of it has, in G, degree at most 6k; this bound being best possible for k even. Moreover, if G has large enough vertices of degree >6k, than it contains a k-path such that each its vertex has degree, in G, at most 5k; this bound is best possible for any k. Received: December 8, 1997 Revised: April 27, 1998     

Approximation algorithms for finding and partitioning unit-disk graphs into co-<Emphasis Type="Italic">k</Emphasis>-plexes

This article studies a degree-bounded generalization of independent sets called co-k-plexes. Constant factor approximation algorithms are developed for the maximum co-k-plex problem on unit-disk graphs. The related problem of minimum co-k-plex coloring that generalizes classical vertex coloring is also studied in the context of unit-disk graphs. We extend several classical approximation results for independent sets in UDGs to co-k-plexes, and settle a recent conjecture on the approximability of co-k-plex coloring in UDGs.     

χ‐bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P₄ (the path on four vertices) similar statements hold. We establish some positive and negative results.     

ON A CONJECTURE ON nTH ORDER DEGREE REGULAR GRAPHS

Abstract

For n a positive integer and v a vertex of a graph G, the nth order degree of v in G, denoted by deg_nv, is the number of vertices at distance n from v. The graph G is said to be nth order regular of degree k if, for every vertex v of G, deg_nv = k. The following conjecture due to Alavi, Lick, and Zou is proved: For n ≥ 2, if G is a connected nth order regular graph of degree 1, then G is either a path of length 2n—1 or G has diameter n. Properties of nth order regular graphs of degree k, k ≥ 1, are investigated.     

On greene's theorem for digraphs

Greene's Theorem states that the maximum cardinality of an optimal k-path in a poset is equal to the minimum k-norm of a k-optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general digraphs in which an optimal k-path contains a path of cardinality one. This implies the validity of the conjecture for all bipartite digraphs. We also extend Greene's Theorem to all split graphs.     

A note on defective colorings of graphs in surfaces

A graph is (m, k)-colorable if its vertices can be colored with m colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. In a recent paper Cowen, Cowen, and Woodall proved that, for each compact surface S, there exists an integer k = k(S) such that every graph in S can be (4, k)-colored. They also conjectured that the 4 could be replaced by 3. In this note we prove their conjecture.