Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition \(E_1 \cup E_2 \cup \cdots \cup E_k\) of the edge set E(G) such that each \(E_i\) induces a locally irregular graph. It was recently conjectured by Baudon et al. that every undirected graph admits a decomposition into at most three locally irregular graphs, except for a well-characterized set of indecomposable graphs. We herein consider an oriented version of this conjecture. Namely, can every oriented graph be decomposed into at most three locally irregular oriented graphs, i.e. whose adjacent vertices have distinct outdegrees? We start by supporting this conjecture by verifying it for several classes of oriented graphs. We then prove a weaker version of this conjecture. Namely, we prove that every oriented graph can be decomposed into at most six locally irregular oriented graphs. We finally prove that even if our conjecture were true, it would remain NP-complete to decide whether an oriented graph is decomposable into at most two locally irregular oriented graphs.     

Contractible Edges in 7-Connected Graphs

An edge of a k-connected graph is said to be a k-contractible edge, if its contraction yields again a k-connected graph. A noncomplete k-connected graph possessing no k-contractible edges is called contraction critical k-connected. Recently, Kriesell proved that every contraction critical 7-connected graph has two distinct vertices of degree 7. And he guessed that there are two vertices of degree 7 at distance one or two. In this paper, we give a proof to his conjecture. The work partially supported by NNSF of China(Grant number: 10171022)     

Kneser's conjecture,chromatic number,and homotopy

If the simplicial complex formed by the neighborhoods of points of a graph is (k ? 2)-connected then the graph is not k-colorable. As a corollary Kneser's conjecture is proved, asserting that if all n-subsets of a (2n ? k)-element set are divided into k + 1 classes, one of the classes contains two disjoint n-subsets.     

Pathwidth, trees, and random embeddings

We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair [12] states that for every minor-closed family of graphs F, there is a constant c(F) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from F is at most c(F). The preceding embedding theorem is used to prove this conjecture whenever the family F does not contain all trees.     

NP-completeness of 4-incidence colorability of semi-cubic graphs

The incidence coloring conjecture, proposed by Brualdi and Massey in 1993, states that the incidence coloring number of every graph is at most Δ+2, where Δ is the maximum degree of a graph. The conjecture was shown to be false in general by Guiduli in 1997, following the work of Algor and Alon. However, in 2005 Maydanskiy proved that the conjecture holds for any graph with Δ?3. It is easily deduced that the incidence coloring number of a semi-cubic graph is 4 or 5. In this paper, we show that it is already NP-complete to determine if a semi-cubic graph is 4-incidence colorable, and therefore it is NP-complete to determine if a general graph is k-incidence colorable.     

On a conjecture of entringer and slater

Entringer and Slater proved that every k-critically h-connected graph with h?2k+1 contains a vertex of degree h and conjectured the existence of two such vertices. We prove this conjecture.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Hamiltonian uniform subset graphs

The uniform subset graph G(n, k, t) is defined to have all k-subsets of an n-set as vertices and edges joining k-subsets intersecting at t elements. We conjecture that G(n, k, t) is hamiltonian when it is different from the Petersen graph and does possess cycles. We verify this conjecture for k − t = 1, 2, 3 and for suitably large n when t = 0, 1.     

Properties of vertex cover obstructions

We study properties of the sets of minimal forbidden minors for the families of graphs having a vertex cover of size at most k. We denote this set by O(k-VERTEX COVER) and call it the set of obstructions. Our main result is to give a tight vertex bound of O(k-VERTEX COVER), and then confirm a conjecture made by Liu Xiong that there is a unique connected obstruction with maximum number of vertices for k-VERTEX COVER and this graph is C_2k+1. We also find two iterative methods to generate graphs in O((k+1)-VERTEX COVER) from any graph in O(k-VERTEX COVER).     

Circuits through specified edges

We prove a theorem implying the conjecture of Woodall [14] that, given any k independent edges in a (k+1)-connected graph, there is a circuit containing all of them. This implies the truth of a conjecture of Berge [1, p.214] and provides strong evidence to a conjecture of Lovász [8].     

On cross-bandwidth

The notion of cross-bandwidth is introduced, and it is shown that any graph that is suitably contractible to a k-connected graph has cross-bandwidth at least k. The contracted edges must induce in the original graph a subgraph of maximum degree at most one. This is used to resolve a conjecture of Erdös and Chinn on the bandwidth of certain graphs.     

Circumference, chromatic number and online coloring

Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k ^2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C ₅ free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.     

A counterexample to the generalization of Sperner's theorem

It has been conjectured that the analog of Sperner's theorem on non-comparable subsets of a set holds for arbitrary geometric lattices, namely, that the maximal number of non-comparable elements in a finite geometric lattice is max w(k), where w(k) is the number of elements of rank k. It is shown in this note that the conjecture is not true in general. A class of geometric lattices, each of which is a bond lattice of a finite graph, is constructed in which the conjecture fails to hold.     

Packing seagulls

A seagull in a graph is an induced three-vertex path. When does a graph G have k pairwise vertex-disjoint seagulls? This is NP-complete in general, but for graphs with no stable set of size three we give a complete solution. This case is of special interest because of a connection with Hadwiger’s conjecture which was the motivation for this research; and we deduce a unification and strengthening of two theorems of Blasiak [2] concerned with Hadwiger’s conjecture. Our main result is that a graph G (different from the five-wheel) with no three-vertex stable set contains k disjoint seagulls if and only if

1. |V (G)|≥3k
2. G is k-connected
3. for every clique C of G, if D denotes the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C then |D|+|V (G)\C|≥2k, and
4. the complement graph of G has a matching with k edges.

We also address the analogous fractional and half-integral packing questions, and give a polynomial time algorithm to test whether there are k disjoint seagulls.     

Tough graphs and hamiltonian circuits

The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t₀, every t₀-tough graph is hamiltonian. Since a square of a k-connected graph is always k-tough, a proof of this conjecture with t₀ = 2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of ($\text{3}\text{2}$)-tough nonhamiltonian graphs.     

Decomposing graphs into paths of fixed length

Barát and Thomassen have conjectured that, for any fixed 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 G has a T-decomposition. The conjecture is trivial when T has one or two edges. Before submission of this paper, the conjecture had been verified only for two other trees: the paths of length 3 and 4, respectively. In this paper we verify the conjecture for each path whose length is a power of 2.     

On diameter critical graphs

A graph G is diameter k-critical if the graph has diameter k and the deletion of any edge increases its diameter. We show that every diameter 2-critical graph on v vertices has (i) at most 0.27v² edges, and (ii) average edge degree at most $\text{6}\text{5}$v. We also make a conjecture on the maximal number of edges in a diameter k-critical graph.     

A counterexample to the Alon-Saks-Seymour conjecture and related problems

Consider a graph obtained by taking an edge disjoint union of k complete bipartite graphs. Alon, Saks, and Seymour conjectured that such graphs have chromatic number at most k+1. This well known conjecture remained open for almost twenty years. In this paper, we construct a counterexample to this conjecture and discuss several related problems in combinatorial geometry and communication complexity.     

Some problems about linear arboricity

We present here a conjecture on partitioning the edges of a graph into k-linear forests (forest whose connected components are paths of length less or equal to k).     

6-regular Cayley graphs on abelian groups of odd order are hamiltonian decomposable

Alspach conjectured that any 2k-regular connected Cayley graph on a finite abelian group A has a hamiltonian decomposition. In this paper, the conjecture is shown true if k=3, and the order of A is odd.