𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Online coloring graphs with high girth and high odd girth

✍ Scribed by J. Nagy-György

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
243 KB
Volume
38
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

(2 + ?)-Coloring of planar graphs with l
(2 + ?)-Coloring of planar graphs with large odd-girth
✍ Klostermeyer, William; Zhang, Cun Quan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 3 views

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. N

On the -optimality in graphs with odd gi
On the -optimality in graphs with odd girth and even girth
✍ C. Balbuena; P. García-Vázquez; L.P. Montejano; J. Salas 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 222 KB

## a b s t r a c t For a connected graph G, the restricted edge-connectivity λ ′ (G) is defined as the minimum cardinality of an edge-cut over all edge-cuts S such that there are no isolated vertices in }, d(u) denoting the degree of a vertex u. The main result of this paper is that graphs with od

Smallest regular graphs with prescribed
Smallest regular graphs with prescribed odd girth
✍ Guo-Hui Zhang 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB 👁 1 views

## Abstract The odd girth of a graph __G__ gives the length of a shortest odd cycle in __G.__ Let __f(k,g)__ denote the smallest __n__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g.__ The exact values of __f(k,g)__ are determined if one of the following holds: __k__

Almost all graphs with high girth and su
Almost all graphs with high girth and suitable density have high chromatic number
✍ Deryk Osthus; Hans Jürgen Prömel; Anusch Taraz 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB 👁 1 views

## Abstract Erdös proved that there exist graphs of arbitrarily high girth and arbitrarily high chromatic number. We give a different proof (but also using the probabilistic method) that also yields the following result on the typical asymptotic structure of graphs of high girth: for all ℓ ≥ 3 and

On the structure of extremal graphs of h
On the structure of extremal graphs of high girth
✍ Lazebnik, Felix; Wang, Ping 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 2 views

Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present sev

The maximum valency of regular graphs wi
The maximum valency of regular graphs with given order and odd girth
✍ Guo-Hui Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

## Abstract The odd girth of a graph __G__ is the length of a shortest odd cycle in __G__. Let __d__(__n, g__) denote the largest __k__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g__. It is shown that __d____n, g__ ≥ 2|__n__/__g__≥ if __n__ ≥ 2__g__. As a consequenc