Talk:List coloring

From Wikipedia, the free encyclopedia

This article is within the scope of the Abandoned Articles WikiProject, a collaborative effort to improve visitation to abandoned articles. If you would like to participate, you can visit the project page, where you can join the project and see a list of open tasks.

This article is within the scope of WikiProject Mathematics.
Mathematics grading:	Start Class	Importance unassessed.	Field: Discrete mathematics

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.