✦ LIBER ✦

On a Conjecture of Woodall

✍ Scribed by Hao Li

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 164 KB
Volume: 86
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2002.2121

No coin nor oath required. For personal study only.

✦ Synopsis

Dirac proved in 1952 that every 2-connected graph of order n and minimum degree k admits a cycle of length at least minfn; 2kg: As a possible improvement, Woodall conjectured in 1975 that if a 2-connected graph of order n has at least n 2 þ k vertices of degree at least k; then it has a cycle of length at least 2k: This conjecture was one of the 50 unsolved problems in Bondy and Murty (''Graph Theory with Applications, '' Macmillan Press, New York, 1976). H. a aggkvist and Jackson showed in 1985 that this conjecture is true if n43k À 2: H. a aggkvist and Li proved that this result is true if the graph is 3-connected. In this paper, we essentially verify Woodall's conjecture.

📜 SIMILAR VOLUMES

Note on a min-max conjecture of Woodall

✍ Orlando Lee; Yoshiko Wakabayashi 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 78 KB

## Abstract In 1978 Woodall [6] conjectured the following: in a planar digraph the size of a shortest cycle is equal to the maximum cardinality of a collection of disjoint tranversals of cycles. We prove that this conjecture is true when the digraph is series‐parallel. In fact, we prove a stronger

One or Two Disjoint Circuits Cover Indep

One or Two Disjoint Circuits Cover Independent Edges: Lovász–Woodall Conjecture

✍ Ken-ichi Kawarabayashi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 408 KB

In this paper, we prove the following theorem: Let L be a set of k independent edges in a k-connected graph G. If k is even or G -L is connected, then there exist one or two disjoint circuits containing all the edges in L. This theorem is the first step in the proof of the conjecture of L.

A short proof of a theorem of dirac's ab

A short proof of a theorem of dirac's about hadwiger's conjecture

✍ D. R. Woodall 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

## Abstract A Short proof is given of the theorem that every grph that does not have __K__~4~ as a subcontraction is properly vertex 3‐colorable.

On a Conjecture of Chalk

✍ Ping Ding 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 261 KB

Let f # Z[x] with degree k and let p be a prime. By a complete trigonometric sum we mean a sum of the form S(q, f )= q x=1 e q ( f (x)), where q is a positive integer and e q (:)=exp(2?if (x)Âq). Professor Chalk made a conjecture on the upper bound of S(q, f ) when q is a prime power. We prove Chalk

On a Conjecture of Foulkes

✍ Suzie C. Dent; Johannes Siemons 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 172 KB

Suppose that ⍀ s 1, 2, . . . , ab for some non-negative integers a and b. Denote Ž . by P a, b the set of unordered partitions of ⍀ into a parts of cardinality b. In this Ž . paper we study the decomposition of the permutation module C P a, b where C is Ž . the field of complex numbers. In particula

On a Conjecture of Ash

✍ Adrian Barbu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 82 KB

In this paper we prove a particular case of a conjecture of Ash that states the existence of Galois representations associated to Hecke eigenclasses in cohomology.