𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Simone Dantas; Sylvain Gravier; Frederic Maffray; Bojan Mohar

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
267 KB
Volume
7
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Extremal graphs for the list-coloring ve
Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum
✍ Simone Dantas; Sylvain Gravier; FrΓ©dΓ©ric Maffray πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 215 KB

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.

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.