✦ LIBER ✦

Extraconnectivity of graphs with large girth

✍ Scribed by J. Fàbrega; M.A. Fiol

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 547 KB
Volume: 127
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)00475-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

UniquelyH-colorable graphs with large gi

UniquelyH-colorable graphs with large girth

✍ Zhu, Xuding 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB 👁 2 views

Suppose G and H are graphs. We say G is H-colorable if there is a homomorphism (edge-preserving vertex mapping) from G to H. We say a graph G is uniquely H-colorable if there is an onto homomorphism c from G to H, and any other homomorphism from G to H is the composition o o c of c with an automorph

4-chromatic graphs with large odd girth

✍ Nguyen Van Ngoc; Zsolt Tuza 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 251 KB

It is known that the Mycielski graph can be generalized to obtain an infinite family of 4-chromatic graphs with no short odd cycles. The first proof of this result, due to Stiebitz, applied the topological method of Lov~sz. The proof presented here is elementary combinatorial.

Domination number of cubic graphs with l

Domination number of cubic graphs with large girth

✍ Daniel Král'; Petr Škoda; Jan Volec 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n / g) < 3n / 10+O(n / g) This research was done when the Petr Škoda was a student of

Total Colourings of Planar Graphs with L

Total Colourings of Planar Graphs with Large Girth

✍ O.V. Borodin; A.V. Kostochka; D.R. Woodall 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 96 KB

It is proved that if G is a planar graph with total (vertex-edge) chromatic number χ , maximum degree and girth g, then χ = + 1 if ≥ 5 and g ≥ 5, or ≥ 4 and g ≥ 6, or ≥ 3 and g ≥ 10. These results hold also for graphs in the projective plane, torus and Klein bottle.

(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

List edge chromatic number of graphs wit

List edge chromatic number of graphs with large girth

✍ A.V. Kostochka 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 785 KB

Kostochka, A.V., List edge chromatic number of graphs with large girth, Discrete Mathematics 101 (1992) 189-201. It is shown that the list edge chromatic number of any graph with maximal degree A and girth at least 8A(ln A + 1.1) is equal to A + 1 or to A. Conjecture 1. The list edge chromatic numbe