𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Extensions of a Conjecture of Gallai

✍ Scribed by André E. Kézdy; Hunter S. Snevily

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
307 KB
Volume
70
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is k-critical if it has chromatic number k but every proper subgraph of G has a (k&1)-coloring. We prove the following result. If G is a k-critical graph of order n>k 3, then G contains fewer than n&3kÂ5+2 complete subgraphs of order k&1.

📜 SIMILAR VOLUMES

Extensions of Gallai–Ramsey results
Extensions of Gallai–Ramsey results
✍ Shinya Fujita; Colton Magnant 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

## Abstract Consider the graph consisting of a triangle with a pendant edge. We describe the structure of rainbow ‐free edge colorings of a complete graph and provide some corresponding Gallai–Ramsey results. In particular, we extend a result of Gallai to find a partition of the vertices of a rain

A note on possible extensions of Negami'
A note on possible extensions of Negami's conjecture
✍ Hlin?n�, Petr 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 2 views

A graph H is a cover of a graph G, if there exists a mapping ϕ from V (H) onto V (G) such that for every vertex v of G, ϕ maps the neighbors of v in H bijectively onto the neighbors of ϕ(v) in G. Negami conjectured in 1987 that a connected graph has a finite planar cover if and only if it embeds in

On a Conjecture of Chalk
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 Woodall
On a Conjecture of Woodall
✍ Hao Li 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 164 KB

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 len

On a Conjecture of Foulkes
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