✦ LIBER ✦

On the number of list-colorings

✍ Scribed by Quentin Donner

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 249 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160307

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given a list of boxes L for a graph G (each vertex is assigned a finite set of colors that we call a box), we denote by f(G, L) the number of L‐colorings of G (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and of size k, f(G, L) = p(G, k), where P=G, k) is the chromatic polynominal of G.

We denote by F(G, k) the minimum of f(G, L) over all the lists of boxes such that each box has size at least k. It is clear that F(G, k) ≤ P(G, k) for all G, k, and we will see in the introduction some examples of graphs such that F(G, k) < P(G, k) for some k. However, we will show, in answer to a problem proposed by A. Kostochka and A. Sidorenko (Fourth Czechoslovak Symposium on Combinatorics, Prachatice, Jin, 1990), that for all G, F(G, k) = P(G, k) for all k sufficiently large. It will follow in particular that F(G, k) is not given by a polynominal in k for all G. The proof is based on the analysis of an algorithm for computing f(G, L) analogous to the classical one for computing P(G, k).

📜 SIMILAR VOLUMES

A note on list-colorings

✍ Amanda Chetwynd; Roland Häggkvist 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

In this article we discuss the current results on the list chromatic conjecture and prove that if G is a triangle free graph with maximum degree A then xi(G) 5 9A/5. If the term "a classic" can be used about a mathematical problem less than 10 years old, then surely the following question by Jeff D

The number of defective colorings of gra

The number of defective colorings of graphs on surfaces

✍ Tom Rackham 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 1 views

A (k, 1)-coloring of a graph is a vertex-coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least c n distinct (4, 1)-colorings, where c is constant and ≈ 1.466 satisfies 3 = 2 +1. On the other hand for any >0, we gi

Oriented list colorings of graphs

✍ Zs. Tuza; M. Voigt 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB 👁 1 views

A 2-assignment on a graph G (V,E) is a collection of pairs Lv of allowed colors speci®ed for all vertices v PV. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satis®es the following property: For every 2-assignment there exists a choic

On the Number of 3-Edge Colorings of Cub

On the Number of 3-Edge Colorings of Cubic Graphs

✍ Christian Szegedy 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In this paper we present a short algebraic proof for a generalization of a formula of R. Penrose, Some applications of negative dimensional tensors, in: Combinatorial Mathematics and its Applications Welsh (ed.), Academic Press, 1971, pp. 221-244 on the number of 3-edge colorings of a plane cubic gr

On the number of discernible colors

✍ C. S. McCamy 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 40 KB 👁 2 views

## On the Number of Discernible On the Number of Discernible Colors Colours I was surprised that, in their study of the number of dis-The authors are grateful to Cal McCamy for his timely cernible colors, Pointer and Attridge 1 missed the early response to their original article. Neither they, nor

On the number of colorings of a snark mi

On the number of colorings of a snark minus an edge

✍ Richard C. Bradley 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB

For a given snark G and a given edge e of G, let (G; e) denote the nonnegative integer such that for a cubic graph conformal to G À feg, the number of Tait colorings with three given colors is 18 Á (G; e). If two snarks G 1 and G 2 are combined in certain well-known simple ways to form a snark G, th