Talk:Graph coloring

From Wikipedia, the free encyclopedia

You have new messages (last change).

On Wikipedia, TeX looks very good when "displayed", thus:

\int_0^\infty 1\,dx

but horrible when embedded in lines of text. Contrast χ(G) with χ(G). If I live forever, I may go through this article and correct it, but in the mean time, maybe those who have been tending to this article can beat me to it. Michael Hardy 21:57, 21 May 2004 (UTC)

OK, I think I've fixed everything. —Caesura(t) 13:22, 25 Apr 2005 (UTC)

Contents

[edit] Problem classification

"The problem of finding a minimum coloring of a graph is NP-hard. The corresponding decision problem (is there a coloring which uses at most k colors?) is NP-complete."

If the decision problem is NP-complete, and there are only N possible answers, doesn't that mean finding a minimum coloring is also NP-complete?

--Dfeuer 00:30, 25 December 2005 (UTC)

No. Only decision problems (problems with yes/no answers) can be NP-complete. However, there are reductions that solve the function problem using the decision problem with a certain number of queries, and this can be used to prove that the function problem lies in a certain class of function problems. For example, binary search will allow you to find the chromatic number with a logarithmic number of queries of the form is there a coloring which uses at most k colors?, which shows that it lies in PNP[log] (see this class at Complexity Zoo). I don't know how many queries you need to actually find a graph coloring, but I'm pretty sure a linear number is enough. Deco 04:29, 25 December 2005 (UTC)
actually, loagrithmic time is enough. In the first run, you find an upper bound by querying 1,2,4,8,16... and then you do a binary search. Honnza 19:12, 12 May 2006 (UTC)
That comment of Deco referred to finding an actual colouring, not to finding the chromatic number. McKay 07:36, 17 May 2006 (UTC)

[edit] k-colorable

The usual meaning of "k-coloring" and "k-colorable" is that there are k colors available, but there is no requirement that each color is actually used. This is frequently unclear in formal definitions but I believe it is what most graph theorists understand. An example from this page where it matters is "If all finite subgraphs of an infinite graph G are k-colorable, then so is G." - this would be vacuous if "k-colorable" required use of all colours (consider the subgraphs with fewer than k vertices). McKay 07:29, 17 May 2006 (UTC)

[edit] graph coloring and maximal clique

(copied from Reference desk, should be incorporated in article probably)

Is there an undirected graph for which the chromatic number exceeds the maximal clique size by more than one?

--Henning

Yes. Mycielski proved in 1955 that for every k\ge1 there is a graph with chromatic number k that contains no triangle subgraphs, that is, whose maximal clique size is just 2. I'll make a drawing of such a graph with chromatic number 4 in a minute. —Bkell (talk) 10:24, 3 July 2006 (UTC)
—Bkell (talk) 10:34, 3 July 2006 (UTC)
Mycielski's proof is actually a constructive proof, so you can use it to make a graph with as large a chromatic number as you like with a maximal clique size of only 2. —Bkell (talk) 10:43, 3 July 2006 (UTC)
J. Mycielski. Sur le coloriage des graphes. Colloq. Math., 3:161–162, 1955. —Bkell (talk) 10:51, 3 July 2006 (UTC)

Thanks a bunch! :)

[edit] Chromatic number and maximal degree

The page says the chromatic number is Δ(G)+1 only when the graph is complete or an odd cycle. It seems that this assumes the graph is connected. If you have a graph whose connected components are all odd cycles or all complete graphs of the same size then the chromatic number and maximal degree are the same as they would be for one component, and so this is another case where the chromatic number is Δ(G)+1.

[edit] For topolgy

I read from Martin Gardner that chromatic number is the maximum regions that can be drawn where every region touches every other region. Joerite 04:44, 1 October 2006 (UTC)

[edit] Graphs only?

Would we want to extend this article to include colorings of the (positive) integers? Or perhaps have another article (linked to the Coloring disambig) wherein colorings on structures besides graphs are explained and/or defined? It would be helpful for things like Van der Waerden's theorem. If anybody wants to add a paragraph or something, go ahead, or I could; but I'd want a go-ahead, since I haven't contributed to or watched this article before. -- 149.43.x.x 07:02, 13 December 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../g/r/a/Talk%7EGraph_coloring_8d41.html"