Verifying Huppert's Conjecture for PSL3(q) and PSU3(q 2)

Let G be a finite group and cd(G) be the set of irreducible character degrees of G. Bertram Huppert conjectured that if H is a finite nonabelian simple group such that cd(G) = cd(H), then G ? H × A, where A is an abelian group. We examine arguments to verify this conjecture for the simple groups of Lie type of rank two. To illustrate our arguments, we extend Huppert's results and verify the conjecture for the simple linear and unitary groups of rank two.     

On characterizing Vizing's edge colouring bound

We consider multigraphs G for which equality holds in Vizing's classical edge colouring bound χ′(G)≤Δ + µ, where Δ denotes the maximum degree and µ denotes the maximum edge multiplicity of G. We show that if µ is bounded below by a logarithmic function of Δ, then G attains Vizing's bound if and only if there exists an odd subset S?V(G) with |S|≥3, such that |E[S]|>((|S| ? 1)/2)(Δ + µ ? 1). The famous Goldberg–Seymour conjecture states that this should hold for all µ≥2. We also prove a similar result concerning the edge colouring bound χ′(G)≤Δ + ?µ/?g/2??, due to Steffen (here g denotes the girth of the underlying graph). Finally we give a general approximation towards the Goldberg‐Seymour conjecture in terms of Δ and µ. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:160‐168, 2012     

Entire colouring of plane graphs

It was conjectured by Kronk and Mitchem in 1973 that simple plane graphs of maximum degree Δ are entirely (Δ+4)-colourable, i.e., the vertices, edges, and faces of a simple plane graph may be simultaneously coloured with Δ+4 colours in such a way that adjacent or incident elements are coloured by distinct colours. Before this paper, the conjecture has been confirmed for Δ?3 and Δ?6 (the proof for the Δ=6 case has a correctable error). In this paper, we settle the whole conjecture in the positive. We prove that if G is a plane graph with maximum degree 4 (parallel edges allowed), then G is entirely 8-colourable. If G is a plane graph with maximum degree 5 (parallel edges allowed), then G is entirely 9-colourable.     

A graph-theoretic version of the union-closed sets conjecture

An induced subgraph S of a graph G is called a derived subgraph of G if S contains no isolated vertices. An edge e of G is said to be residual if e occurs in more than half of the derived subgraphs of G. We introduce the conjecture: Every non-empty graph contains a non-residual edge. This conjecture is implied by, but weaker than, the union-closed sets conjecture. We prove that a graph G of order n satisfies this conjecture whenever G satisfies any one of the conditions: δ(G) ≤ 2, log₂ n ≤ δ(G), n ≤ 10, or the girth of G is at least 6. Finally, we show that the union-closed sets conjecture, in its full generality, is equivalent to a similar conjecture about hypergraphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 155–163, 1997     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

Menger's theorem for infinite graphs with ends

A well‐known conjecture of Erd?s states that given an infinite graph G and sets A, ? V(G), there exists a family of disjoint A ? B paths ?? together with an A ? B separator X consisting of a choice of one vertex from each path in ??. There is a natural extension of this conjecture in which A, B, and X may contain ends as well as vertices. We prove this extension by reducing it to the vertex version, which was recently proved by Aharoni and Berger. © 2005 Wiley Periodicals, Inc. J Graph Theory 50: 199–211, 2005     

Graphic Sequences Have Realizations Containing Bisections of Large Degree

A bisection of a graph is a balanced bipartite spanning sub‐graph. Bollobás and Scott conjectured that every graph G has a bisection H such that deg_H(v) ≥ ?deg_G(v)/2? for all vertices v. We prove a degree sequence version of this conjecture: given a graphic sequence π, we show that π has a realization G containing a bisection H where deg_H(v) ≥ ?(deg_G(v) ? 1)/2? for all vertices v. This bound is very close to best possible. We use this result to provide evidence for a conjecture of Brualdi (Colloq. Int. CNRS, vol. 260, CNRS, Paris) and Busch et al. (2011), that if π and π ? k are graphic sequences, then π has a realization containing k edge‐disjoint 1‐factors. We show that if the minimum entry δ in π is at least n/2 + 2, then π has a realization containing edge‐disjoint 1‐factors. We also give a construction showing the limits of our approach in proving this conjecture. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Matroidal families of finite connected nonhomeomorphic graphs exist

A matroidal family is a nonempty set ? of connected finite graphs such that for every arbitrary finite graph G the edge sets of the subgraphs of G which are isomorphic to an element of ? form a matroid on the edge set of G. In the present paper the question whether there are any matroidal families besides the four previously described by Simões-Pereira is answered affirmatively. It is shown that for every natural number n ? 2 there is a matroidal family that contains the complete graph with n vertices. For n = 4 this settles Simões-Pereira's conjecture that there is a matroidal family containing all wheels.     

The forcing number of graphs with given girth

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The forcing number, originally known as the zero forcing number, and denoted F (G), of G is the cardinality of a smallest forcing set of G. We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth g of a graph is the length of a shortest cycle in the graph. Let G be a graph with minimum degree δ ≥ 2 and girth g ≥ 3. Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that F (G) ≥ δ + (δ ? 2)(g ? 3). This conjecture has recently been proven for g ≤ 6. The conjecture is also proven when the girth g ≥ 7 and the minimum degree is sufficiently large. In particular, it holds when g = 7 and δ ≥ 481, when g = 8 and δ ≥ 649, when g = 9 and δ ≥ 30, and when g = 10 and δ ≥ 34. In this paper, we prove the conjecture for g ∈ {7, 8, 9, 10} and for all values of δ ≥ 2.     

Cycle covers of graphs with a nowhere-zero 4-flow

It is shown that the edges of a simple graph with a nowhere-zero 4-flow can be covered with cycles such that the sum of the lengths of the cycles is at most |E(G)| + |V(G)| ?3. This solves a conjecture proposed by G. Fan.     

The Edge Correlation of Random Forests

The conjecture was made by Kahn that a spanning forest F chosen uniformly at random from all forests of any finite graph G has the edge-negative association property. If true, the conjecture would mean that given any two edges ε₁ and ε₂ in G, the inequality \mathbbP(e₁ ? F, e₂ ? F) ￡ \mathbbP(e₁ ? F)\mathbbP(e₂ ? F){{\mathbb{P}(\varepsilon_{1} \in \mathbf{F}, \varepsilon_{2} \in \mathbf{F}) \leq \mathbb{P}(\varepsilon_{1} \in \mathbf{F})\mathbb{P}(\varepsilon_{2} \in \mathbf{F})}} would hold. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices. We derive explicit related results for random trees.     

The Solution of Length Five Equations Over Groups

Let G be a group, t an unknown, and r(t) an element of the free product G* ? t?. The equation r(t) = 1 has a solution over G if it has a solution in a group H containing G. The Kervaire–Laudenbach (KL) conjecture asserts that if the exponent sum of t in r(t) is nonzero the equation has a solution. Equations of length 5 have been studied and it was proved that a solution exists under certain restrictions imposed on the coefficients of the equation. This article removes these restrictions and therefore settles the KL conjecture for equations of length five.     

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.     

Proof of a tiling conjecture of Komlós

A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χ_cr(H)))n, where χ_cr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003     

The chromatic index of graphs with a spanning star

Vizing's Theorem states that any graph G has chromatic index either the maximum degree Δ(G) or Δ(G) + 1. If G has 2_s + 1 points and Δ(G) = 2s, a well-known necessary condition for the chromatic index to equal 2_s is that G have at most 2s² lines. Hilton conjectured that this condition is also sufficient. We present a proof of that conjecture and a corollary that helps determine the chromatic index of some graphs with 2s points and maximum degree 2s ? 2.     

On the maximum number of pairwise compatible euler cycles

B. Jackson [4] made the following conjecture: If G is an Eulerian graph with δ(G) ≥ 2k, then G has a set of 2k - 2 pairwise compatible Euler cycles (i.e., every pair of adjacent edges appears in at most one of these Euler cycles as a pair of consecutive edges). We verify this conjecture in the case where every circuit of G is a block of G.     

The longest cycle of a graph with a large minimal degree

We show that every graph G on n vertices with minimal degree at least n/k contains a cycle of length at least [n/(k ? 1)]. This verifies a conjecture of Katchalski. When k = 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2n then G is Hamiltonian.     

FINITELY GENERATED G′ AND POSITIVE LAWS

We conjecture that a finitely generated relatively free group G has a finitely generated commutator subgroup G′ if and only if G satisfies a positive law. We confirm this conjecture for groups G in the large class, containing all residually finite and all soluble groups.     

The Normalizer Property for Integral Group Rings of Complete Monomial Groups

Abstract

Let G be a complete monomial group with nilpotent base, namely, G = N wr Sym _m , the wreath product of a finite nilpotent group N with the symmetric group on m letters. Then G satisfies the normalizer conjecture for ?G.     

Uniquely Edge-3-Colorable Graphs and Snarks

 A cubic graph G is uniquely edge-3-colorable if G has precisely one 1-factorization. It is proved in this paper, if a uniquely edge-3-colorable, cubic graph G is cyclically 4-edge-connected, but not cyclically 5-edge-connected, then G must contain a snark as a minor. This is an approach to a conjecture that every triangle free uniquely edge-3-colorable cubic graph must have the Petersen graph as a minor. Fiorini and Wilson (1976) conjectured that every uniquely edge-3-colorable planar cubic graph must have a triangle. It is proved in this paper that every counterexample to this conjecture is cyclically 5-edge-connected and that in a minimal counterexample to the conjecture, every cyclic 5-edge-cut is trivial (an edge-cut T of G is cyclic if no component of G\T is acyclic and a cyclic edge-cut T is trivial if one component of G\T is a circuit of length |T|). Received: July 14, 1997 Revised: June 11, 1998