Seymour's Second Neighborhood Conjecture for Tournaments Missing a Generalized Star

Seymour's Second Neighborhood Conjecture asserts that every digraph (without digons) has a vertex whose first out‐neighborhood is at most as large as its second out‐neighborhood. We prove its weighted version for tournaments missing a generalized star. As a consequence the weighted version holds for tournaments missing a sun, star, or a complete graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:89–94, 2012     

Supereulerian Digraphs with Large Arc‐Strong Connectivity

Let D be a digraph and let be the arc‐strong connectivity of D, and be the size of a maximum matching of D. We proved that if , then D has a spanning eulerian subdigraph.     

Arc‐Disjoint Cycles and Feedback Arc Sets

Isaak posed the following problem. Suppose T is a tournament having a minimum feedback arc set, which induces an acyclic digraph with a hamiltonian path. Is it true that the maximum number of arc‐disjoint cycles in T equals the cardinality of minimum feedback arc set of T? We prove that the answer to the problem is in the negative.     

Arc‐Disjoint In‐ and Out‐Branchings With the Same Root in Locally Semicomplete Digraphs

Deciding whether a digraph contains a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex is a well‐known NP‐complete problem (as proved by Thomassen, see 2 ). This problem has been shown to be polynomial time solvable for semicomplete digraphs 2 and for quasi‐transitive digraphs 6 . In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from 2 for semicomplete digraphs and solves an open problem from 4 .     

On a Generalization of the Ryser‐Brualdi‐Stein Conjecture

A rainbow matching for (not necessarily distinct) sets of hypergraph edges is a matching consisting of k edges, one from each . The aim of the article is twofold—to put order in the multitude of conjectures that relate to this concept (some first presented here), and to prove partial results on one of the central conjectures.     

Schanuel's Conjecture and Algebraic Roots of Exponential Polynomials

In this article, I will prove that assuming Schanuel's conjecture, an exponential polynomial with algebraic coefficients can have only finitely many algebraic roots. Furthermore, this proof demonstrates that there are no unexpected algebraic roots of any such exponential polynomial. This implies a special case of Shapiro's conjecture: if p(x) and q(x) are two exponential polynomials with algebraic coefficients, each involving only one iteration of the exponential map, and they have common factors only of the form exp (g) for some exponential polynomial g, then p and q have only finitely many common zeros.     

Hadwiger's Conjecture for ℓ‐Link Graphs

In this article, we define and study a new family of graphs that generalizes the notions of line graphs and path graphs. Let G be a graph with no loops but possibly with parallel edges. An ?‐link of G is a walk of G of length in which consecutive edges are different. The ?‐link graph of G is the graph with vertices the ?‐links of G , such that two vertices are joined by edges in if they correspond to two subsequences of each of μ ‐links of G . By revealing a recursive structure, we bound from above the chromatic number of ?‐link graphs. As a corollary, for a given graph G and large enough ?, is 3‐colorable. By investigating the shunting of ?‐links in G , we show that the Hadwiger number of a nonempty is greater or equal to that of G . Hadwiger's conjecture states that the Hadwiger number of a graph is at least the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (Eur J Combin 25(6) (2004), 873–876) for line graphs, and hence 1‐link graphs. We prove the conjecture for a wide class of ?‐link graphs.     

Regular Hypertournaments and Arc‐Pancyclicity

A k‐hypertournament H on n vertices () is a pair , where V is the vertex set of H and A is a set of k‐tuples of vertices, called arcs, such that for all subsets with , A contains exactly one permutation of S as an arc. Recently, Li et al. showed that any strong k‐hypertournament H on n vertices, where , is vertex‐pancyclic, an extension of Moon's theorem for tournaments. In this article, we examine several generalizations of regular tournaments and prove the following generalization of Alspach's theorem concerning arc‐pancyclicity: Every Σ‐regular k‐hypertournament on n vertices, where , is arc‐pancyclic.     

A Note on the History of the Four‐Colour Conjecture

The four‐colour conjecture was brought to public attention in 1854, most probably by Francis or Frederick Guthrie. This moves back by six years the date of the earliest known publication.     

Dade's Invariant Conjecture for the Symplectic Group Sp4(2 n ) and the Special Unitary Group SU4(22n ) in Defining Characteristic

In this article, we verify Dade's projective invariant conjecture for the symplectic group Sp₄(2 ⁿ ) and the special unitary group SU₄(2²ⁿ ) in the defining characteristic, that is, in characteristic 2. Furthermore, we show that the Isaacs–Malle–Navarro version of the McKay conjecture holds for Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) in the defining characteristic, that is, Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) are good for the prime 2 in the sense of Isaacs, Malle, and Navarro.     

Uno's Invariant Conjecture for the Finite Symplectic Group Sp4(q) in the Defining Characteristic

The purpose of this article is to study a categorification of the n-th tensor power of the spin representation of U(𝔰𝔬(7, ?)) by using certain subcategories and projective functors of the Bernstein–Gelfand–Gelfand (BGG) category of the complex Lie algebra 𝔤𝔩 _n .     

Claw‐Free Graphs,Skeletal Graphs,and a Stronger Conjecture on ω, Δ, and χ

The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw‐free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw‐free graphs with a three‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs.     

A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture

A well‐known combinatorial theorem says that a set of n non‐collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance‐hereditary graphs.     

二部图形式的Erd\H{O}s-S\'{o}s猜想

二部图形式的Erd\H{O}s-S\''{o}s猜想     

An Asymptotic Version of the Multigraph 1‐Factorization Conjecture

We give a self‐contained proof that for all positive integers r and all , there is an integer such that for all any regular multigraph of order 2n with multiplicity at most r and degree at least is 1‐factorizable. This generalizes results of Perkovi? and Reed (Discrete Math 165/166 (1997), 567–578) and Plantholt and Tipnis (J London Math Soc 44 (1991), 393–400).     

The Merrifield–Simmons Conjecture Holds for Bipartite Graphs

Let be a graph and the number of independent (vertex) sets of G. Then the Merrifield–Simmons conjecture states that the sign of the term only depends on the parity of the distance of the vertices in G. We prove that the conjecture holds for bipartite graphs by considering a generalization of the term, where vertex subsets instead of vertices are deleted.     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008     

Hadwiger's Conjecture for the Complements of Kneser Graphs

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers , the Kneser graph is the graph with vertices the k‐subsets of an n‐set such that two vertices are adjacent if and only if the corresponding k‐subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs.     

The ultra‐weak Ash conjecture and some particular cases

Ash's functions N _{σ ,k} count the number of k ‐equivalence classes of σ ‐structures of size n . Some conditions on their asymptotic behavior imply the long standing spectrum conjecture. We present a new condition which is equivalent to this conjecture and we discriminate some easy and difficult particular cases. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)