𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a conjecture by Plummer and Toft

✍ Scribed by Hor?�k, Mirko; Jendrol', Stanislav

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
175 KB
Volume
30
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

The cyclic chromatic number χ c (G) of a 2-connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G such that, for every face-bounding cycle f of G, the vertices of f have different colors. Plummer and Toft proved that, for a 3-connected plane graph G, under the assumption ∆ * (G) ≥ 42, where ∆ * (G) is the size of a largest face of G, it holds that χ c (G) ≤ ∆ * (G)+4. They conjectured that, if G is a 3-connected plane graph, then χ c (G) ≤ ∆ * (G) + 2. In the article the conjecture is proved for ∆ * (G) ≥ 24.

📜 SIMILAR VOLUMES

On a conjecture of Thomassen and Toft
On a conjecture of Thomassen and Toft
✍ Kriesell, Matthias 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 2 views

This article is motivated by a conjecture of Thomassen and Toft on the number s 2 (G) of separating vertex sets of cardinality 2 and the number v 2 (G) of vertices of degree 2 in a graph G belonging to the class G of all 2-connected graphs without nonseparating induced cycles. Let G denote the numbe

On a conjecture of Aris: Proof and remar
On a conjecture of Aris: Proof and remarks
✍ Dan Luss; Neal R. Amundson 📂 Article 📅 1967 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 428 KB 👁 2 views
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

Proof of a conjecture on cycles in a bip
Proof of a conjecture on cycles in a bipartite graph
✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 2 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. W