Talk:List coloring

Definition of k-choosability

The article seems to say that each vertex has its own list of colors to choose from. But this makes the description of choosability incomprehensible. --MarSch 15:01, 11 December 2006 (UTC)

The article is correct. Choosability k means: for any lists of k colors assigned to vertices, there is a proper vertex coloring. These lists do not have to be the same. They can be pairwise distinct, for example.Then it is easy to see that there is a proper coloring. 212.35.31.33 23:19, 19 January 2007 (UTC)

actually, i think it's not "k colors", k should be the size of the list.

That's what I said. Each vertex has a list containing k colors. It does not matter what exactly these k colors _are_ with repect to other lists.

Every graph seems to be 1-choosable. --MarSch 19:10, 28 January 2007 (UTC)

No! Any graph with at least one edge is not 1-choosable, as there is a clear way to assign 1-element lists so that the graph is not colorable. Remember, k-list-colorable means that _any_ assignment of k-element lists permits a proper vertex coloring.

You seem to assume that the colors are to be different. That would make sense, but I don't think the article says this yet.--MarSch 11:04, 3 February 2007 (UTC)

I think there's some confusion here. The colors in each list can be arbitrarily chosen. The lists _can_ be pairwise distinct. They can also all be identical, or anything inbetween. In list coloring we are making assertions about any set of such lists: k-list-colorable in an n-vertex graph means for _any_ n lists of k colors, the graph has a proper vertex coloring using these lists. There is no restriction on the contents of the lists.

I'm sorry if I'm not managing to make this clear. It is not a very easy concept to explain.

From the article: "More precisely, a list coloring is a choice function that maps every vertex to a color from a prescribed list for that vertex.". So let's have a graph with two vertices and let the list for each vertex be {red}. Now I choose as list coloring red for each vertex. Clearly you cannot choose less colors to make the list coloring impossible; something is wrong with the definition.--MarSch 09:33, 6 February 2007 (UTC)

I have read the definition more closely, and I also now think that it is wrong.
The definition omits that k-list-colorability requires that there be a _proper_ list coloring for any assignment of k-lists to vertices. Otherwise you are right: any graph would be 1-colorable under the curent wording.
Is this definition now more clear? I think also "for every collection of lists of k colors" is correct, but not very nice. "for any assignment of k-element lists to the vertices" may be more clear.

if now you would also add the definition of proper --MarSch 16:31, 6 February 2007 (UTC)

I wanted to link to it, but I couldn't really find a suitable anchor in the article on graph coloring (or in the glossary of graph theory article). I think we can safely assume anyone interested in graph list coloring knows what a proper vertex coloring is?

No, we cannot.--MarSch 11:48, 7 February 2007 (UTC)

I still do not see why not. (I also don't see why you don't make any changes yourself if you have such certain opinions!). Nevertheless I have changed it, and the definition of list edge-coloring. I'm of the opinion that it is absolutely stupid to define a basic concept in the middle of this definition, and that there should simply be a linkable definition of proper coloring somewhere. As it stands each article on coloring has to include a definition of 'proper', which ia both ugly and redundant.

I suspected that it was something to do with colors having to be different, but I wasn't sure, and I also knew that someone else knew for certain, so it seemed appropriate to get them to add the info. Graph_coloring#Vertex_coloring also has the explanation of "proper". Perhaps List edge-coloring and List coloring could be merged there. --MarSch 13:53, 8 February 2007 (UTC)

Sorry, I somehow had the impression that you knew what it was. I don't think it's a good idea to merge the 2 list-coloring articles. If that's done then all the other coloring variants should be merged and that would make the graph coloring article a bit long.

Choice number and chromatic number

I wonder where is the citation for the claim that the choice number of a graph G is at most log(n) times the chromatic number of that graph, G. I doubt that this has been proven yet. —Preceding unsigned comment added by 217.132.85.169 (talk) 15:27, 6 September 2008 (UTC)

The result is claimed as known in this talk, though I haven't yet tracked down an authoritative source. –Erik Demaine (talk) 01:46, 29 September 2008 (UTC)

And a proof of the result is provided in the second part of the talk, though I haven't yet tracked down an authoritative source. 134.176.28.77 (talk) 07:42, 15 July 2009 (UTC)

mechanical jibberish

a lot of this article comprises of words that a normal person wouldnt understand. can someone change this so i can understan d it. thank, James Fitzpatrick —Preceding unsigned comment added by 217.23.4.35 (talk) 00:10, 30 January 2010 (UTC)