𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum

✍ Scribed by Simone Dantas; Sylvain Gravier; Frédéric Maffray

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
215 KB
Volume
141
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We characterize the graphs G such that Ch(G) + Ch( G) = n + 1, where Ch(G) is the choice number (list-chromatic number) of G and n is its number of vertices.

📜 SIMILAR VOLUMES

A list version of Dirac's theorem on the
A list version of Dirac's theorem on the number of edges in colour-critical graphs
✍ Alexandr V. Kostochka; Michael Stiebitz 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 2 views

## Abstract One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 (1941) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension o

A six-color theorem for the edge-face co
A six-color theorem for the edge-face coloring of plane graphs
✍ Cuiqin Lin; Guanzhang Hu; Zhongfu Zhang 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 218 KB

It was shown (Kronk and Mitchen, 1973) that the set of vertices, edges and faces of any normal map on the sphere can be colored with seven colors. In this paper we solve a somewhat different problem: the set of edges and faces of any plane graph with A ~< 3 can be colored by six colors.