✦ LIBER ✦

On 3-colorable non-4-choosable planar graphs

✍ Scribed by Voigt, M.; Wirth, B.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 72 KB
Volume: 24
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199703)24:3<233::aid-jgt4>3.0.co;2-q

No coin nor oath required. For personal study only.

✦ Synopsis

An L-list coloring of a graph G is a proper vertex coloring in which every vertex v gets a color from a list L(v) of allowed colors. G is called k-choosable if all lists L(v) have exactly k elements and if G is L-list colorable for all possible assignments of such lists. Verifying conjectures of Erdős, Rubin and Taylor it was shown during the last years that every planar graph is 5-choosable and that there are planar graphs which are not 4-choosable. The question whether there are 3-colorable planar graphs which are not 4-choosable remained unsolved. The smallest known example far a non-4-choosable planar graph has 75 vertices and is described by Gutner. In fact, this graph is also 3 colorable and answers the above question. In addition, we give a list assignment for this graph using 5 colors only in all of the lists together such that the graph is not List-colorable.

📜 SIMILAR VOLUMES

On total 9-coloring planar graphs of max

On total 9-coloring planar graphs of maximum degree seven

✍ Sanders, Daniel P.; Zhao, Yue 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 2 views

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If ∆(G) is the maximum degree of G, then no graph has a total ∆-coloring, but Vizing conjectured that every graph has a total (∆ + 2)-coloring. This Total Coloring Conjecture rem

On convex embeddings of planar 3-connect

On convex embeddings of planar 3-connected graphs

✍ Kelmans, Alexander 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 2 views

A well-known Tutte's theorem claims that every 3-connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3-connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in thi

Non-injured maize contains several 1,4-b

Non-injured maize contains several 1,4-benzoxazin-3-one related compounds but only as glucoconjugates

✍ Vincent Cambier; Thierry Hance; Edmond de Hoffmann 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB

DIMBOA (2,4-dihydroxy-7-methoxy-1,4-benzoxazin-3-one) and its derivatives are known to participate in the resistance of the Poaceae to several pests. A more efficient analytical method for the determination of these compounds is reported, employing high performance liquid chromatography coupled with

Cover Picture: Fabrication of Stable Met

Cover Picture: Fabrication of Stable Metallic Patterns Embedded in Poly(dimethylsiloxane) and Model Applications in Non-Planar Electronic and Lab-on-a-Chip Device Patterning (Adv. Funct. Mater. 4/2005)

✍ K. J. Lee; K. A. Fosser; R. G. Nuzzo 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB 👁 1 views

Surface-Enhanced Resonance Raman Scatter

Surface-Enhanced Resonance Raman Scatteringof a Thin Film of the Non-Linear Optic Material4-(N,N-Dimethylamino)-3-acetamidonitrobenzene Grown on Potassium Acid Phthalate

✍ J. McAleese; B. N. Rospendowski; D. B. Sheen; J. N. Sherwood; W. E. Smith 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB 👁 1 views

Raman scattering from a layer of the non-linear optic material 4-(N,N-dimethylamino)-3-acetamidonitrobenzene (DAN) deposited on a 001 cleavage face of a potassium acid phthalate crystal and on glass were obtained following deposition of a coating of silver on the surface of the material. By choosing

Fast Atom Bombardment Mass Spectrometric

Fast Atom Bombardment Mass Spectrometric and Tandem Mass Spectrometric Investigation in Thioglycerol on Protonated Non-covalentAssociations of β-Cyclodextrin with 2-Acetyl,2-Propionyl-1-pyrroline and 5-Acetyl-2,3-dihydro-1,4-thiazine, Roast Smelling Odorants in Food. Role of the Matrix

✍ Mele, Andrea; Panzeri, Walter; Selva, Antonio 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB

2-Acetyl-1-pyrroline (1), 2-propionyl-1-pyrroline (2) and 5-acetyl-2,3-dihydro-1,4-thiazine (3), roast smelling odorants in food, form stable inclusion compounds with b-cyclodextrin. Fast atom bombardment (FAB) mass spectra of such complexes in thioglycerol showed abundant [ G + Hs + Mx + H ] ' ions