✦ LIBER ✦

A conjecture of Borodin and a coloring of Grünbaum

✍ Scribed by Dieter Rautenbach

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 114 KB
Volume: 58
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20299

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every k color classes with 1 ≤ k ≤ 4 induces a (k—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139–147, 2008

📜 SIMILAR VOLUMES

Grünbaum colorings of toroidal triangula

Grünbaum colorings of toroidal triangulations

✍ Michael O. Albertson; Hannah Alpert; sarah-marie belcastro; Ruth Haas 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

## Abstract We prove that if __G__ is a triangulation of the torus and χ(__G__)≠5, then there is a 3‐coloring of the edges of __G__ so that the edges bounding every face are assigned three different colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 68–81, 2010

On a list coloring conjecture of Reed

✍ Tom Bohman; Ron Holzman 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 54 KB

## Abstract We construct graphs with lists of available colors for each vertex, such that the size of every list exceeds the maximum vertex‐color degree, but there exists no proper coloring from the lists. This disproves a conjecture of Reed. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 106–10

A counterexample to the rank-coloring co

A counterexample to the rank-coloring conjecture

✍ N. Alon; P. D. Seymour 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

It has been conjectured by C. van Nuffelen that the chromatic number of any graph with at least one edge does not exceed the rank of its adjacency matrix. We give a counterexample, with chromatic number 32 and with an adjacency matrix of rank 29.

Proof of a Conjecture of Frankl and Füre

Proof of a Conjecture of Frankl and Füredi

✍ Gurumurthi V. Ramanan 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 375 KB

We give a simple linear algebraic proof of the following conjecture of Frankl and Fu redi [7,9,13]. (Frankl We generalise a method of Palisse and our proof-technique can be viewed as a variant of the technique used by Tverberg to prove a result of Graham and Pollak [10,11,14]. Our proof-technique

Diagonal 11-coloring of plane triangulat

Diagonal 11-coloring of plane triangulations

✍ Oleg V. Borodin 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## Abstract The vertices of each plane triangulation without loops and multiple edges may be colored with 11 colors so that for every two adjacent triangles [__xyz__] and [__wxy__], the vertices __x__,__y__,__w__,__z__ are colored pairwise differently.

Cyclic degree and cyclic coloring of 3-p

Cyclic degree and cyclic coloring of 3-polytopes

✍ Borodin, Oleg V. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 402 KB 👁 1 views

A vertex coloring of a plane graph is called cyclic if the vertices in each face bounding cycle are colored differently. The main result is an improvement of the upper bound for the cyclic chromatic number of 3-polytopes due to Plummer and Toft, 1987 (J. Graph Theory 11 (1 987) 505-51 7). The proof