text:
Talk:Graph coloring

Running Time
Source for the claims in the info box? All I found was: http://www.cs.lu.se/home/Thore_Husfeldt/papers/xsat.pdf

A graph’s chromatic number is the smallest integer � � n such that there is a mapping V ! {1, . . ., �} that gives different values (‘colours’) to neighbouring vertices. This is a well-studied problem with a rich history of exponential-time algorithms.

We provide two such algorithms, based on divide-and-conquer in time O(8.33n), and based on inclusion–exclusion in time O(2.4423n). —Preceding unsigned comment added by Voyager2378 (talk • contribs) 01:49, 23 April 2010 (UTC)

 * I think the paper you're looking for is http://www.cs.lu.se/home/Thore_Husfeldt/papers/Set_partitioning_via_inclusion-exclusion.pdf (published in SIAM J. Computing 2006). I'm not sure why it isn't cited in the article or mentioned in the text of the article, though. —David Eppstein (talk) 03:03, 23 April 2010 (UTC)
 * False modesty. I did some soul-searching with respect to including references to my own work, and left some parts in a messier state than I should. Thore Husfeldt (talk) 06:43, 23 April 2010 (UTC)
 * Thank you. BTW I'am very bad at editing... but IMHO somebody should put the reference next to the running time:O(n*2^n) in "the info box". I know that it is in the text. Just a suggestion.  —Preceding unsigned comment added by 94.253.171.1 (talk) 21:32, 23 April 2010 (UTC)

Embedded TeX
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 $$\chi(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)

To the contrary - As Nils Grimsmo pointed out to me, usage of the tag is, by default, only rendered with TeX if the expression is sufficiently complicated. If it's simple, it will display in a textual manner which still looks better than the regular plain text. You can change this in the math section of your user preferences if you do not like how your math is being rendered. So, it's mostly best to go with using math tags everywhere, and let the viewer decide what works best. ~ Booya Bazooka 09:20, 17 December 2006 (UTC)

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)

Computational Complexity
The article currently says "Graph coloring remains NP-complete even on planar graphs of degree at most 4 [with reference to Garey and Johnson]." It should be improved to read "Graph coloring remains NP-complete even on planar graphs of degree 4 [with reference to David P. Dailey: Uniqueness of Colorability and Colorability of Planar 4-regular Graphs are NP-complete. Discrete Mathematics 1980, 30:289-293. ].David.daileyatsrudotedu (talk) 11:54, 21 August 2009 (UTC)

 * Please go ahead and make that change — see WP:Be Bold. —David Eppstein (talk) 13:56, 21 August 2009 (UTC)

There is a discrepancy between this article and the article on bipartite graphs. This article says that a breadth first search can be used to ascertain whether a graph can be colored with two colors. The article on bipartite graphs describes it as a depth-first search (using pre-order, which is only applicable to depth-first searches). The article on bipartite graphs seems to be the correct one. — Preceding unsigned comment added by 69.140.29.212 (talk) 17:49, 5 June 2014 (UTC)
 * They are both correct. Either kind of search will work. —David Eppstein (talk) 18:30, 5 June 2014 (UTC)

The article states "for every k > 3, a k-coloring of a planar graph exists [...], and it is possible to find such a coloring in polynomial time.", without giving any source for that claim. (I'm struggling to find a source for it.) Please add a source for this claim, or clarify that it's trivial (is it?). — Preceding unsigned comment added by 81.97.161.110 (talk • contribs) 18:52, 22 September 2020 (UTC)
 * Sources can be found in Four color theorem. —David Eppstein (talk) 19:05, 22 September 2020 (UTC)

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)

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)

 * [[Image:Grötzsch_graph.svg|250px]] —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! :)

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.

- Quite right; this is Brooks' Theorem and seems to be included correctly now. Adking80 20:12, 13 July 2007 (UTC)

For topology
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)

I also think that maximal chromaticity of any downwards closed family of graphs (as are graphs ebbeddable on a ___) is equal to the size of the largest Kn belonging to the family, or equally, that any graph not containing Kn are (n-1)colorable. Proof for one to three colors is straightforward. But I'm not sure on K5-forbidden graphs (the non-planar ones) and higherHonnza 12:55, 14 January 2007 (UTC)

 * It sounds to me like you're talking about Hadwiger's Conjecture, which posits that a graph is (k-1)-colourable unless it contains a K_k minor. This has been proven for k at most six.  Adking80 20:16, 13 July 2007 (UTC)

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)
 * Since this article is called Graph coloring, it should clearly go to another article. But feel free to create one. --Mellum 11:31, 16 December 2006 (UTC)

Computing the chromatic polynomial
Perhaps someone who understands this a bit better can help to clarify this section, because it seems a bit unclear. The confusing bit is how the text refers to $$e$$, "the edge". What edge? Just any arbitrary edge, no matter which edge is chosen? I have a small amount of experience with the deletion-contraction algorithm (just used it on simple cycle graphs $$C_n$$) and still don't fully understand the article text, so I really don't think it's layperson-friendly enough. ~ Booya Bazooka 09:14, 17 December 2006 (UTC)

New page on Discharging Method
I recently created a page on the Discharging Method. Would anyone be willing to read it any and give some feedback? Thanks. Ptrillian 07:26, 2 January 2007 (UTC)

Definition of "proper"
Most pages on specific colorings seem to have to define the term proper. This is not very nice and also detracts IMO from the legibility of definitions. Is it worth creating a separate page to define proper colorings (or maybe just have a distinct section of this article - can you link to them specifically in wiki markup?) that other pages can link to? —Preceding unsigned comment added by 129.132.208.80 (talk • contribs) 12:48, 7 February 2007

Interpretations of chromatic polynomials with complex roots
Could something perhaps be added with respect to chromatic polynomials with complex roots, such as the cp of the petersen graph?

Tutte polynomial etc.
The Tutte polynomial of a matroid might be worth mentioning, since it's a sort of generalization of the chromatic polynomial. LDH 05:05, 14 April 2007 (UTC)

Welsh and Powell - note
Could someone find a better example to illustrate the non-optimality of Welsh-Powell algorithm? The example with the star is plainly wrong... Making the steps of the algorithm listed in the article will color the star with 2 colors. —The preceding unsigned comment was added by 83.131.41.128 (talk) 17:11, 1 May 2007 (UTC).

Colouring Squares, Triangles and Hexagons
query - is this the correct article for this item - I am looking for a section on 'recreational maths puzzles'.

The 2-section-Square

With 2 colours has 3 forms (a2, ab, b2).

With 3 colours there are 6 forms ( as above plus ac, bc, c2)

With 4 colours there are 10 forms (as above plus ad, bd, cd & d2);

- The 4-section-Square

The opportunities for recreational patterning vary considerably depending if the square is divided diagonally or orthogonally. The numbers alter if rotational or reflection variants are or are not allowed.

With 2 colours has 6 forms; (a4, a3b, a2b2, ab3, b4 & abab);

With 3 colours there are 24 forms (of which 3 are reflections);

With 4 colours there are 66 forms (of which 12 are reflections). There are 6 forms which use all 4 colours.

- The 3-section-Triangle

With 2 colours has 4 forms; (a3, a2b, ab2, b3);

With 3 colours it has 13 forms depending as to whether 'abc' is "the same" as 'acb'.

As with the 4-section square, the patterns vary depending whether the triangle is divided corner-wise or edge-wise.

- The 6-section-Hexagon

With 2 colours has 13 forms;

a6; a5b; a4b2; a3b3; a2b4; ab5; b6 plus the 'middle 3' variants aabaab & abaaab; aababab & abbaab; abbabb & ababbb.

As an example of a recreational maths puzzle, these thirteen hexes can be fitted with edge-matching into what shapes?

With 3 colours and depending on the reflection rules adopted - there are 76 variants.

There are opportunities for using these to make puzzles and for other recreational mathematics JK-Salisbury 86.160.138.236 (talk) 14:08, 3 June 2008 & 27 June 2008 (UTC)

 * You want to count the number of different colorings of small cycle graphs? The closest I can think of to a correct article for that would be chromatic polynomial, although it does not factor out the symmetries. —David Eppstein (talk) 14:49, 3 June 2008 (UTC)

Loop cannot be legally colored?
What does this mean : "Whenever G contains a loop, it cannot be legally colored at all" ? —Preceding unsigned comment added by 72.48.91.143 (talk) 16:45, 16 July 2008 (UTC)
 * Both endpoints of a loop are the same vertex, so it is impossible for the loop to have different colors at its endpoints. —David Eppstein (talk) 16:51, 16 July 2008 (UTC)

Graph coloring = vertex coloring, other comments
I’ve looked at this page from the outside of a long while, and think the topic could make a  wonderful and quite accessible article. There are some things I’d like to do, but at least one of them is potentially contentious because it’s the defining first sentence, so I’d better take it up here first: currently the article’s first definition is agnostic about which elements of the graph are coloured (edges, vertices, or both). This is the proper “mathy” way of doing it, I understand that it’s tempting to be as general as possible, but 99% of the article, and most other occurrences of the term, refer specifically to vertex colouring. So I’d like the article to define graph colouring as vertex colouring and leave the variants (edge colouring, general graph labelling) out of the introduction. (Of course they should appear later.)

Specifically, the first sentences could be whittled down to this:
 * In graph theory, a graph coloring is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color.

(If we’re looking for outside sources, many textbooks use that definition anyway. Toft and Jensen, for example.)

The sections on chromatic polynomials and the list of variants are comparatively long and detailed, so maybe these could be moved to separate articles eventually. Let me also announce that sooner or later I may reach a Citing oneself conflict of interest in the algorithms section. Thore Husfeldt (talk) 09:59, 2 December 2008 (UTC)

Should we do infoboxes? Horse and helium and sheet bends have them. Should computational problems? I’m not sure. Currently they’re just tables instead of proper infobox templates. What I like is that it displays useful information in a compact as accessible fashion. Argument against would be that the whole article is in danger of placing undue emphasis on the algorithmic aspect of the problem. Comments? Thore Husfeldt (talk) 09:56, 11 December 2008 (UTC)

 * I like the idea of having infoboxes for computational problem. In addition to the "algorithmic" information that you have in your examples, I suggest that we add more "combinatorial" information that interlinks different problems. (For example, the infobox for clique could tell that it is equal to independent set in the complement graph. The infobox for dominating set could tell that a maximal independent set is a dominating set. The infobox for vertex cover could tell that it is a special case of set cover. The infobox for edge coloring could refer to vertex coloring in the line graph, etc.) To save some space, it might be a good idea to combine the infoboxes for graph coloring & chromatic number (and domatic partition & domatic number, etc.) – after all, many (algorithmic) results are related to both of them. One question: would you put the infobox on the Dominating set page or on the Dominating set problem page or both? There are several similar cases where there are two pages for one problem. — Miym (talk) 12:05, 11 December 2008 (UTC)
 * Ad your question: looking at a few examples, I can’t actually see a good reason why Dominating set and Dominating set problem are different pages, nor Covering (graph theory) and Vertex cover problem. I think that the Graph coloring algorithm is a much better model for how these things should be organised. Thore Husfeldt (talk) 14:14, 11 December 2008 (UTC)
 * I absolutely agree with you; many things (reading, editing, linking) would be easier if we always had just a page "X" and not "X problem". Unfortunately some people seem to oppose merging "X" and "X problem"; see, e.g., Talk:Independent set problem. — Miym (talk) 14:52, 11 December 2008 (UTC)
 * The opposition seems be regarding merging Foo to Foo problem. But lets see. I’ll start the merger proposal again. Thore Husfeldt (talk) 20:45, 14 December 2008 (UTC)

Distributed graph coloring?
Should we mention distributed (or parallel) algorithms for graph coloring here? I was thinking about classics like the Cole–Vishkin (1986) algorithm for 3-coloring an n-cycle in $$O(\log^* n)$$ time, and Linial's (1992) seminal $$\Omega(\log^* n)$$ lower bound. One could also briefly mention some generalisations that give a distributed $$(\Delta+1)$$-coloring in poly($$\Delta$$) + $$O(\log^* |V|)$$ time. — Miym (talk) —Preceding undated comment was added at 21:35, 17 December 2008 (UTC).
 * That, and on-line graph coloring. Go ahead. Thore Husfeldt (talk) 05:45, 18 December 2008 (UTC)
 * Yes please. :-) I'll review the new content. Dcoetzee 22:48, 18 December 2008 (UTC)

Order of references?
What is the order of references in the end of the page? Should it be alphabetical or the order of reference or something else? Miym (talk) 20:53, 21 December 2008 (UTC)
 * Alphabetical. I tried to clean them up, but didn’t sort them, because I hoped to find a tool that would do just that for me. Thore Husfeldt (talk) 21:23, 21 December 2008 (UTC)
 * I don't know of a lot of tools for working with Wikipedia bibliography templates. There's http://zeteo.info/ but I think that's more for individual bibliographies than sorting whole bibliography sections. I have an application I wrote myself that can read and write bibtex files, edit entries in them, and convert to and from the Wikipedia citation templates — it doesn't currently know how to spit out more than one template at a time, but it does know how to sort people by last name, so likely it could be made to work for this task as well. Just a small matter of programming. But the user interface only works on OS X versions 10.5 or greater and though I'd be happy to share it individually I don't think it's ready for public distribution yet. —David Eppstein (talk) 21:45, 21 December 2008 (UTC)

New Algorithm Solves The Colouring Problem An Order Of Magnitude More Quickly
...or should that be the counting problem? Somebody with a more detailed understanding can correct me if necessary. It appears to use graph theory algebra to achieve the claimed result. There's an overview article here: http://www.physorg.com/news153588084.html and there's a PDF containing more detail about how the algorithm works at http://www.iop.org/EJ/article/1367-2630/11/2/023001/njp9_2_023001.pdf New Thought (talk) 22:04, 12 February 2009 (UTC)
 * This looks like a legitimate paper, but it's about the counting version of the problem (which is much more difficult), not the decision version. See Sharp P for more details. Dcoetzee 22:36, 12 February 2009 (UTC)
 * ... or to Tutte polynomial, where I already wrote a section on computation, since the paper essentially solves the general problem. But from a brief look, I find it difficult to summarise the contribution of the linked result -- especially, I could not quickly find a description of what they compare their performance to. Thore Husfeldt (talk) 06:17, 13 February 2009 (UTC) Later edit: scratch that. It would belong to the Algorithms section of Chromatic polynomial. Thore Husfeldt (talk) 08:26, 13 February 2009 (UTC)

NP-completeness of planar 3-colorability, attribution
The attribution for NP-completeness for 3-colorability of planar graphs of degree 4 was changed from Garey, Johnsson, Stockmeyer to Dailey. I don’t have online access to the Discrete Mathematics volume from 1980 (I could get that tomorrow.) Is the improvement in the Dailey-paper the restriction to regular graphs? Thore Husfeldt (talk) 10:45, 26 August 2009 (UTC)

See above discussion under Computational Complexity. The change was indeed because of the restriction to regular graphs of degree four. I can restrict it further to regular graphs of degree four which have a tangle number of one (citing my dissertation of 1978), but that gets a little esoteric for the purpose I think. David.daileyatsrudotedu (talk) 04:22, 22 December 2009 (UTC)

Brute Force search
I can't believe the formula, $$\scriptstyle\binom{n}{k}$$, given here for the number of possible assignments, valid or not, of k colors to n nodes. Note that this evaluates to $$2(n-1)/2$$ for the case k = 2, instead of the $$2^n-2$$ I would expect. Shouldn't the number be something like $$k^n$$, for assigning at most k colors, or like $$\sum_{i=0}^{k}\binom{k}{i}{(k-i)}^{n}{(-1)}^{i}$$ for assigning exactly k colors?--192.4.227.200 (talk) 19:27, 19 October 2009 (UTC)

 * You're right. I think the original editor meant $$\left\{\begin{matrix} n \\ k \end{matrix}\right\}$$ (Stirling numbers of the second kind). I'm still not sure how the O(n!) upper bound arises though, since the brute force algorithm should stop when a valid colouring is found, having time complexity O(kn) at most. I'm editing the article to reflect this, someone correct me if I'm wrong. --Robin (talk) 03:41, 20 October 2009 (UTC)
 * On second thought, computing the Chromatic polynomial is not the same as computing the Chromatic number. I've left the upper bound as it is, but I've changed the n choose k to n brace k, which is what the editor probably meant in the first place. --Robin (talk) 03:50, 20 October 2009 (UTC)
 * Strange indeed. I suspect these are my own descriptions; I don’t know what I was thinking. I’ll replace the description by something simpler. Thore Husfeldt (talk) 09:47, 20 October 2009 (UTC)

TeX solecisms
My comments above stand, and in the mean time I've found a bunch of stuff like this:
 * $$\chi (G) \,$$ ≤ $$ \Delta (G) \,$$
 * $$\chi (G) \,$$ ≤ $$ \Delta (G) \,$$

This should look like this:
 * $$\chi (G) \le \Delta (G) \, $$
 * $$\chi (G) \le \Delta (G) \, $$

Michael Hardy (talk) 20:03, 24 October 2009 (UTC)
 * I agree that mixing TeX and html like this is wrong, but for this particular example, what's wrong with formatting it in pure HTML, e.g.
 * χ(G) ≤ Δ(G)
 * ? That way the formula size matches the text size rather than being (in my browser) about twice as tall. —David Eppstein (talk) 21:25, 24 October 2009 (UTC)

Placement of pictures
The article contains this large picture:

It was placed on the left. I've changed the placement to the right side, and rearranged its placement. I think its distracting to have it on the left. Also, I believe we could decrease the height of this picture by displaying the Y-axis only up to 20, instead of 30. Any comments on the rearrangement / reduction of image size? --Robin (talk) 19:50, 3 November 2009 (UTC)

Color/Colour
Given the history of the four colour problem, and the early study of similar problems being a practically solely English thing, why is this article spelt the american way? —Preceding unsigned comment added by 134.219.202.104 (talk) 11:02, 1 April 2010 (UTC)
 * Because the first major contributor used American English. See WP:ENGVAR. VMS Mosaic (talk) 02:11, 2 April 2010 (UTC)

 * You're never going to win this one. I am currently submitting a paper which is full of American spellings and it kills me! Unfortunately colorability as a computational problem has been a largely american endeavour, and the entire mathematical community with the exception of Britain and Canada seem to have accept color as standard. My coauthor is Russian for example. Triangl (talk) 15:37, 10 April 2011 (UTC)

Algorithms section
How about creating sub sections for sequential and parallel algorithms? — Preceding unsigned comment added by Überfuzz (talk • contribs) 15:10, 14 August 2014 (UTC)

Other applications subsection
Should the sentence "The problem of coloring a graph has found a number of applications, including pattern matching" be removed? There is no source to back it up, there is no explanation in this article of how graph colouring applies to pattern matching, nor is it explained in the article on pattern matching. Mathmoose (talk) 01:05, 23 October 2014 (UTC)

Unable to understand the reason of an added section being removed from Graph Coloring
Dear Dr. Eppstein,

I fail to understand the ground behind not considering the following section in the Graph Coloring wiki page (https://en.wikipedia.org/wiki/Graph_coloring).

I received your note. I was not really into an edit-war. It's just that after consuming comments like "heavily promotional" or "overlong description", I had to review the section and make necessary language modifications to make the text aligned with the rest of the page. So it was a language edit while the content was virtually the same. The added new section takes the opportunity to discuss 'sequential coloring' through the 'trailing path' algorithm. The approach is novel, special and unmistakably leads to a significant advancement in the subject. It should, therefore, be part of a 'first reading' article about graph coloring.

I would further like to add that the 'trailing path' algorithm was published in Soft Computing (https://link.springer.com/article/10.1007/s00500-019-04278-8), a decades-long, well-praised journal in the field (current IF: 2.78), covered by most major available citation indexes. So, I am not really sure nor am I convinced about the rational basis of editorial comments like "underwhelming heuristic published in a bad journal"! Rather, it would be of much help to have more constructive elaborative and precise criticism giving a scope to identify and rectify flaws (if applicable).

-

Sequential coloring: The trailing path algorithm

There have been many attempts to solve the Graph coloring Problem through a couple of centuries now (from Francis Guthrie, 1852) wherein many combinatorial optimization algorithms have been invoked. However, no algorithm was found to procure an exact solution of the chromatic number comprehensively for any and all graphs within the polynomial (P) time domain. Recently a novel heuristic, namely the ‘trailing path’ [30] could reset this state of the art. The 'trailing path' algorithm have shown to return an approximate solution of the chromatic number within P time with a better accuracy than existing algorithms, working unanimously irrespective of the graph-size and topology, working particularly well for the most difficult k-regular graphs (k>2). In its design, ‘trailing path’ effectively turns out to be a subtle combination of the search patterns of two existing heuristics (DSATUR [31] and largest first (LF) [32]) with contrasting approaches; and operates along a trailing path of consecutively connected nodes. LF colors nodes in the descending order of their degrees while DSATUR opts to color nodes in the descending order of their color saturation (i.e., the number of colors that can NOT be used to color a node - as has been found at a certain step of coloring). It naturally follows that both approaches effectively implement discontinuous coloring schemes (i.e., there is no guarantee that two nodes colored one after the other would remain connected in the original graph). The 'trailing path' approach meticulously amalgamates the two aforementioned search patterns of LF and DSATUR and furthermore operates through a trailing path of consecutively connected nodes (i.e., a sequential coloring scheme) in contrast to the earlier approaches. It thereby also effectively maps to the problem of finding spanning tree(s) of the graph during the entire course of coloring - where essentially lies both the novelty and the apt of this approach. Adaptation of sequential coloring is an interesting new addition to the state of the art in Graph Coloring and has the potential to serve other partitioning / compartmentalization problems in combinatorics.

-

Nemo8130 (talk) 20:03, 28 December 2019 (UTC)

Sankar Basu

Assistant Professor, Asutosh College (Under Calcutta University, Kolkata, India)

PhD: Saha Institute of Nuclear Physics, Kolkata, India

Post Docs: FfAME, FL, USA; Linkoping University, Sweden; University of Calcutta, India; University of Delhi, India; Clemson University, USA; ULB, Brussels, Belgium

Core Area: Computational Biophysics and Bioinformatics

--

 * It's a newly published paper, in a bad journal, with no citations and hence no reliable sourcing for its impact. It does not solve the graph coloring problem exactly (or if it claims to, it's pure crankery) so the overblown history about how nobody has ever solved it before is just pure promotion and is misleading. It does not yet stand out from the other 45000 or so papers on graph coloring listed by Google Scholar, so there is no justification for including it. And your edits appear to be motivated by an undeclared conflict of interest. The correct solution is to not add it, not to keep arguing. —David Eppstein (talk) 20:02, 28 December 2019 (UTC)

---

1. >> "It's a newly published paper, in a bad journal"

- Your excellency, here is this bad journal's website: https://www.springer.com/journal/500 and its editporial board page: https://www.springer.com/journal/500/editors. We would appriciate if you could kindly care to justify your comment with some facts and figures, or else, such loose comments really sound childish!

2. >> "with no citations and hence no reliable sourcing for its impact"

- Your excellency, the online-first version of the paper was published in the web, little more than two months back. The off-line regular article is scheduled to be printed and included in the journal's first issue of January 2020. So I am not sure whether the number of citations at this stage could be a correct and just yardstick to assess its merit.

3. >> "overblown history about how nobody has ever solved it before "

- The 'graph coloring' wiki-page discusses about different strategies adopted to develop Combinatorial Optimization algorithms wherein a key approach ('sequential coloring') is found missing. To aid this void, we intended to compare between discontinuous (LF, DSATUR) and continuous coloring schemes ('trailing path') and suggested intuitively as to why continuous coloring schemes have been found to be performing better (for this one has to read the paper). Kindly note with care, the sentence: "It thereby also effectively maps to the problem of finding spanning tree(s) of the graph during the entire course of coloring". This is key point in Graph Coloring and even if his excellency denies I regret I would beg to differ. There were no promotional intentions otherwise.

3. >> "It does not yet stand out from the other 45000 or so papers on graph coloring listed by Google Scholar" - We shall be grateful if his excellency could kindly bring to our site, one paper among the "45000 or so papers on graph coloring listed by Google Scholar" that procures an exact solution of chromatic number unanimously for all graphs. We shall be grateful to unlearn and relearn.

4. >> "It does not solve the graph coloring problem exactly" - Let me quote from the above text drafted for the section.

"Recently a novel heuristic, namely the ‘trailing path’ [30] could reset this state of the art. The 'trailing path' algorithm have shown to return an approximate solution of the chromatic number within P time with a better accuracy than existing algorithms, working unanimously irrespective of the graph-size and topology, working particularly well for the most difficult k-regular graphs (k>2)."

My understanding of the English language does not reflect any claim to output an exact solution, rather, it says 'an approximate solution with better accuracy'. I don't think the two are the same.

5. >> "not to keep arguing" We had the idea that Wikipedia was a global educational forum that appreciates scholastic excellence. We were not aware of this practice of new editorial 'monopoly' here.

-- Nemo8130 (talk) 05:45, 29 December 2019 (UTC)
 * Ok, so amid your walls of text you're now clearly claiming that your paper gives an "exact solution of chromatic number unanimously for all graphs"? In polynomial time? At least that makes it clear that it's crankery and not merely weakly-justified new heuristics. For this sort of claim, I have a very clear answer to when it can go into Wikipedia: when it wins the Clay Millenium Prize for proving P=NP.
 * You should probably also read Copying text from other sources, by the way, as copying material from non-freely-licensed copyrighted material into Wikipedia is very much forbidden. —David Eppstein (talk) 06:16, 29 December 2019 (UTC)

-- >> you're now clearly claiming that your paper gives an "exact solution of chromatic number unanimously for all graphs"? In polynomial time?

No sir. That is something that you are making out of the text. It appears that you are too much obsessed to falsify our claim without actually realizing what the claim is! I would humbly request you to kindly take care to read the text. If I may know your email id, I can send you the pdf of the paper (also available here: https://link.springer.com/article/10.1007/s00500-019-04278-8 - if you have access to download).

Let me again quote from the text and try to clarify:

1. "The trailing path algorithm has shown to return an approximate solution of the chromatic number within P time with a better accuracy than existing algorithms, working unanimously irrespective of the graph-size and topology, working particularly well for the most difficult k-regular graphs (k>2)."

And, furthermore,

2. To address your point on "45000 or so papers on graph coloring from Google Scholar", I said that we do not yet know of a method that procures an exact solution of the chromatic number unanimously for all graphs (within P time, of course).

So the point we are trying to make in this drafted section (and also in the paper) is that 'trailing path' performs better than the state-of-the-art before and we further try to highlight the importance of opting for 'sequential coloring'/* for this improved performance.

/* the term is mentioned just once in the Graph Coloring wiki page under 'greedy algorithms'

Nemo8130 (talk) 15:58, 29 December 2019 (UTC)

Again: "proper"
Sorry, but I still don't understand the distinction between a vertex coloring (in general) and a proper vertex coloring (in particular). Is it similar to a subset and a proper subset? Is a vertex coloring just an assignment of labels to vertices? Is the extra condition for proper that no two adjacent vertices have the same color? The answers may be obvious to graph theory experts, but I don't see them in the text (maybe I have a blind spot here?). I'm pretty sure that vertex coloring (in general) isn't defined in the first pararaph of Graph_coloring.

Moreover, I found the "(proper)" occurrences in the following paragraphs disturbing. I'm inclined to read them similar to e.g. "The converse of a (strict) order is again a (strict) order", i.e. as a short form for two sentences, but this doesn't seem to make sense. - Jochen Burghardt (talk) 19:32, 13 July 2021 (UTC)
 * It's not an issue of mathematical distinctions but of varying nomenclature. What it means is:
 * The default meaning, when people in this area say "coloring" without a modifier, is an assignment of labels to vertices so that edges have two distinct endpoint labels.
 * Sometimes, instead, authors use "coloring" to mean an unconstrained assignment of labels to vertices, but because this conflicts with the default meaning this variation needs to be called out by those authors to avoid confusion.
 * The authors who use "coloring" in the unconstrained way use "proper coloring" to mean a coloring that is constrained in the usual way.
 * Some authors, even while using "coloring" in the constrained way, sometimes use "proper coloring" as a way of emphasizing those constraints, or as a way of signalling that they are following the default convention.
 * Our article uses "proper" in the same way, as an emphasis on the constraints of the coloring and as a signal that we are talking about the conventional notion of graph coloring.
 * If you think there is some clearer way of wording this, please consider a change of wording, but I think the article does already adequately describe this issue.
 * —David Eppstein (talk) 19:47, 13 July 2021 (UTC)

Question about Ramsey numbers section
Hi all, Wikipedia and graph theory newbie here. I just wanted to check whether there was a small error or not in the section on Ramsey numbers in this article. The excerpt in question is: "An important class of improper coloring problems is studied in Ramsey theory, where the graph's edges are assigned to colors, and there is no restriction on the colors of incident edges. A simple example is the friendship theorem, which states that in any coloring of the edges of $$K_{6}$$, the complete graph of six vertices, there will be a monochromatic triangle; often illustrated by saying that any group of six people either has three mutual strangers or three mutual acquaintances." I might be wrong on this, but shouldn't the wikilink actually go to the page called Theorem on friends and strangers? --QB2k (talk) 05:51, 7 December 2022 (UTC)

 * Yes, thanks for noticing that. I have edited the article to correct this. Cheers! DoctorMatt (talk) 07:13, 7 December 2022 (UTC)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Talk:Graph coloring


text:
User:Julien~enwiki

Julien Catalano, born in Lozère, France. I speak French (Mother tongue), English and Spanish. My interests are in Linux and more generally in Free software.

Graduated from École centrale de Marseille, Engineer school in Marseille, France.

Now Research scientist in Philips Research Eindhoven, the Netherlands.

If you are a French speaker, you can also visit my french wikipedia user page.

Tools
New pages : Search for small articles to be completed...

Random! I am lucky

articles in Wikipedia

My contributions on the User Edit Counter

Personal notes
diff command to generate a patch file for Patch (Unix) diff -uNr dirname.orig dirname > dirname-why.patch

fr:Utilisateur:Julien Catalano

Release date test
This test is aimed to modify Template:release date in order to display 1 day ago instead of 1 days ago.

latest_preview_date   =

5949 days days ago ago

title: User:Julien~enwiki


text:
David, Chiriquí

David, known as David City in colonial times, is a city and corregimiento in the west of Panama. It is the capital of the province of Chiriquí and has an estimated population of 82,907 inhabitants as confirmed in 2013. It is a relatively affluent city with a firmly established, dominant middle class and a very low unemployment and poverty index. The Pan-American Highway is a popular route to David. It is named after the Biblical King David. David is the largest city in Panama that is not part of the Panama city metro area.

The development of the banking sector, public construction works such as the expansion of the airport and the David-Boquete highway alongside the growth of commercial activity in the city have increased its prominence as one of the fastest-growing regions in the country. The city is the economic center of the Chiriqui province and produces more than half the gross domestic product of the province, which totals 2.1 billion. It is known for being the third-largest city in the country both in population and by GDP and for being the largest city in Western Panama.

History
David was founded in 1602, by the governor Juan López de Siqueira. The city had been founded in the area where the Bolivar park is currently located. In those times, the city was divided into three regions, one fit for Spanish residence, and another two of lesser areas known as "San Antonio de Padra", "David" and "Nuestra Señora del Rosario". At the end of the 19th century, David had six streets, but only four were populated, making up the city center, in the sector currently known as Barrio Bolívar. The Ermita de San José (currently the San José Cathedral) was located in that area. In March 1900, the Bolívar Park was the scene of the first battle of the "Thousand Days' War", between liberals and conservatives who would later march on towards the capital to wage war against each other.

By 1726, the city was not recognized by the central government, even though intellectuals and other important people resided within the city boundaries. Juan Lopez de Sequeira is considered the main intellectual of the city and Francisco de Gama is credited as being responsible for the creation of the city. Both were converted Jewish people. It is speculated that the religious differences between them and the Royal Audience of Panama were the reason the latter refused to recognize them as such; however, in 1736, the city finally received recognition from the colonial government and was named "La Ermita San Jose de David".

From 1916 to 1949, the Chiriqui province had access and employed a railway system, having been created by Belisario Porras to accelerate the development of the province and the exploitation of the agrarian products produced en masse by the province. The 165-kilometer-long railway system had its base of operations and main stations in the city and cemented its importance as a merchant city for the western region of Panama.

According to ancient documents, the name of the city was the idea of the local natives. Also, it was the rest stop of the long trail that connected the rest of Central America with Panama City, known as the "Camino Real" or "Royal Trail".

The city's airport, Enrique Malek International Airport, previously called David Field or San Jose Field during World War II, was an auxiliary of Howard Field. It accommodated a variety of United States Army Air Forces personnel, dedicated for the most part in training and reconnaissance missions over the Southeast Pacific coastline, from Honduras in the north, to Peru in the south as part of the defense of the Panama Canal.

University

 * Universidad Autónoma de Chiriquí
 * Universidad Santa Maria La Antigua
 * Universidad Tecnologica de Chiriquí
 * ULACIT Chiriquí
 * Columbus University

International schools:
 * American School

Commerce and industrialization
San José de David (official name) is Panama's third largest urban area. It functions as a hub for the province's commercial activities, mainly agriculture and cattle raising and supplies the rest of the country. It is the region's chief financial center and most national banks have offices here, including international banks such as HSBC. It also serves as a port of exports and imports with neighboring Costa Rica. It is connected to the rest of the country by the Pan-American Highway, and the Enrique Malek International Airport. David is one of the most industrialized cities in the country and is a center of manufacturing, heavy industry and high technology standards and communications. It is also a popular tourist destination due to its nightlife, entertainment, cuisine, shopping and relative proximity to the Pacific coast and the Panamanian highlands.

Location and geography

David is located in a basin in south central Chiriquí Province between the cities of Puerto Armuelles on the coast and Boquete in the mountains. The city lies below the water break on the David River, at the foothills of the Cordillera de Talamanca mountain range. Volcán Barú, a potentially active volcano and also the tallest mountain in Panama, is visible from northern parts of the city. David is roughly 30 km from the Costa Rican border and is a vital center for trade between the two countries, located some 434 km from Panama City.

The city has little geographic variations within its boundaries. The main geographic landmarks in David are “Cerro San Cristobal” and “Cerro Pedregal”, located in the southern area of the city, in the Pedregal area. Mounts “Cerro Santa Cruz” and the “Pico de Loro” (literally: “Parrot’s Peak”) Sierra surround the north of David, being located in the San Carlos Area.

David's northeast region is surrounded by the Manjagua and David rivers, dividing David from the residential “Las Lomas” area. There are also smaller rivers running in a southernly direction and feeding the Pedregal estuary, which surrounds Pedregal and reaches its delta near the grounds of the Enrique Malek International Airport.

The ocean coast close to David is in part covered by extensive beaches and mangroves. The city's main port, Pedregal, is located in the south end of the city, near the mangrove-filled region. The port is closely connected by land to the city's airport. This port is the docking site for small private vessels and yachts owned by David's residents, and also serves as an attraction for fishers. It is also the departing place for tours that go to the numerous islands of the Chiriquí Gulf and the base of operations of many handicraft vendors.

The city is the seat of the Roman Catholic Diocese of David.

Climate
The city has one of the hottest climates in the Central American region, but the temperatures drop sharply near the outskirts. David's climate is classified as a tropical monsoon climate (Köppen Am) with a short, sweltering, dry season from mid-December to mid-April and a long, oppressive and hot wet season from mid-April to mid-December.

Layout
Central David is mostly laid out in a grid with numbered streets; however, the streets on the outskirts of town are neither named nor numbered. David's population density is rather low, as most people live in detached single-family homes. Most buildings in town, including those in the central business district, are only one or two stories high. Only a few hotels, banks, casinos, and apartment buildings reach a height of two to five stories.

Most expatriates and the wealthiest residents live in the northern section of the city and in the neighboring communities immediately to the north and northwest. This area is also a commercial district and contains many franchises, stores and outlets.

David offers many lodging options. As Chiriquí province continues to gain popularity as a tourist destination, more hotels are being built to accommodate all budget ranges. Hotels in the city present the visitor with a wide variety of amenities and variety of prices. The hotels are located in the city center, near the banking and business district so they have the most central location of the city. Many backpackers and budget travelers have recently discovered David. There are two main backpacker hostels: Bambu Hostel and Purple House. The area is also home to the Miguel de Cervantes Saavedra Park. The central location makes the base from which Chiriqui's main chains and companies operate and serves as the headquarters and banking center of many banks in the province.

The Miguel de Cervantes Saavedra Park is located in the middle of the city. This new park works as a rest stop for visitors and locals traversing the city. It is known for offering shade from the city's usual sunny weather under its trees. It is the place of business for some ice cream, handicraft and lottery vendors, and is surrounded by banks, hotels and many shops.

Notable residents

 * José Luis Lacunza Maestrojuán - Cardinal of Panama
 * Carlos Ruiz - Baseball player, Philadelphia Phillies
 * Rosa Montezuma - fashion model and Señorita Panamá 2018

title: David, Chiriquí


text:
John Young (naval officer)

John Young (c. 1740–1781) was a captain in the Continental Navy during the American Revolutionary War, commander of the USS Saratoga (1780) which was lost at sea.

Background
He began his seafaring career at an early age in the colonial merchant marine and, at the start of the American Revolution, was commissioned 23rd on the list of captains in the Continental Navy. On 20 September 1776, the Continental Congress directed Young to take the sloop-of-war USS Independence (1776 sloop) to Martinique to protect American mercantile shipping in the West Indies. Collaterally, Independence was to raid British shipping whenever the opportunity arose.

On 5 July 1777, Young was ordered to Nantes, France, and subsequently arrived at Lorient with two prizes. On 17 February 1778, while in French waters, he sailed through the French Fleet, saluting that nation's government with a 13-gun salute. In return he received a nine-gun salute, one of the earliest salutes rendered by the French government to the fledgling American government. At the time, John Paul Jones was on board Independence.

Young returned to America in the spring of 1778 and successively commanded two Pennsylvania privateers, Buckskin and Impertinent, before he was given command of the sloop-of-war USS Saratoga (1780) - then fitting out at Philadelphia—in May 1780. Young took her to sea on 13 August 1780 and, in the course of the ship's first cruise, captured one prize before she returned to port for repairs and alterations.

Subsequent cruises were more successful, as Young commanded Saratoga on three more sweeps at sea in which he took a total of eight more prizes. Young proved himself a daring and resourceful commander. On one occasion, he took Saratoga between two British ships and captured both. Largely as a result of his dedication and emphasis on training, Saratoga compiled a distinguished, but altogether brief, record before her untimely and unexplained loss.

Saratoga set sail from Cap-Haïtien, in what is now Haiti, on 15 March 1781. After taking a prize three days later, the sloop-of-war became separated from her later that day when a strong gale swept through the area, the high winds nearly swamping the prize commanded by Midshipman Penfield. After the storm passed by, Saratoga was nowhere to be seen, having vanished without a trace.

The United States Navy named two ships, USS Young (DD-312), and USS John Young (DD-973) in his honor.

title: John Young (naval officer)


text:
Perfect graph theorem

In graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

Statement
A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph. Perfect graphs include many important graphs classes including bipartite graphs, chordal graphs, and comparability graphs.

The complement of a graph has an edge between two vertices if and only if the original graph does not have an edge between the same two vertices. Thus, a clique in the original graph becomes an independent set in the complement and a coloring of the original graph becomes a clique cover of the complement.

The perfect graph theorem states:

 * The complement of a perfect graph is perfect.

Equivalently, in a perfect graph, the size of the maximum independent set equals the minimum number of cliques in a clique cover.

Example
Let G be a cycle graph of odd length greater than three (a so-called "odd hole"). Then G requires at least three colors in any coloring, but has no triangle, so it is not perfect. By the perfect graph theorem, the complement of G (an "odd antihole") must therefore also not be perfect. If G is a cycle of five vertices, it is isomorphic to its complement, but this property is not true for longer odd cycles, and it is not as trivial to compute the clique number and chromatic number in an odd antihole as it is in an odd hole. As the strong perfect graph theorem states, the odd holes and odd antiholes turn out to be the minimal forbidden induced subgraphs for the perfect graphs.

Applications
In a nontrivial bipartite graph, the optimal number of colors is (by definition) two, and (since bipartite graphs are triangle-free) the maximum clique size is also two. Also, any induced subgraph of a bipartite graph remains bipartite. Therefore, bipartite graphs are perfect. In n-vertex bipartite graphs, a minimum clique cover takes the form of a maximum matching together with an additional clique for every unmatched vertex, with size n − M, where M is the cardinality of the matching. Thus, in this case, the perfect graph theorem implies Kőnig's theorem that the size of a maximum independent set in a bipartite graph is also n − M, a result that was a major inspiration for Berge's formulation of the theory of perfect graphs.

Mirsky's theorem characterizing the height of a partially ordered set in terms of partitions into antichains can be formulated as the perfection of the comparability graph of the partially ordered set, and Dilworth's theorem characterizing the width of a partially ordered set in terms of partitions into chains can be formulated as the perfection of the complements of these graphs. Thus, the perfect graph theorem can be used to prove Dilworth's theorem from the (much easier) proof of Mirsky's theorem, or vice versa.

Lovász's proof
To prove the perfect graph theorem, Lovász used an operation of replacing vertices in a graph by cliques; it was already known to Berge that, if a graph is perfect, the graph formed by this replacement process is also perfect. Any such replacement process may be broken down into repeated steps of doubling a vertex. If the doubled vertex belongs to a maximum clique of the graph, it increases both the clique number and the chromatic number by one. If, on the other hand, the doubled vertex does not belong to a maximum clique, form a graph H by removing the vertices with the same color as the doubled vertex (but not the doubled vertex itself) from an optimal coloring of the given graph. The removed vertices meet every maximum clique, so H has clique number and chromatic number one less than that of the given graph. The removed vertices and the new copy of the doubled vertex can then be added back as a single color class, showing that in this case the doubling step leaves the chromatic number unchanged. The same argument shows that doubling preserves the equality of the clique number and the chromatic number in every induced subgraph of the given graph, so each doubling step preserves the perfection of the graph.

Given a perfect graph G, Lovász forms a graph G* by replacing each vertex v by a clique of tv vertices, where tv is the number of distinct maximum independent sets in G that contain v. It is possible to correspond each of the distinct maximum independent sets in G with one of the maximum independent sets in G*, in such a way that the chosen maximum independent sets in G* are all disjoint and each vertex of G* appears in a single chosen set; that is, G* has a coloring in which each color class is a maximum independent set. Necessarily, this coloring is an optimal coloring of G*. Because G is perfect, so is G*, and therefore it has a maximum clique K* whose size equals the number of colors in this coloring, which is the number of distinct maximum independent sets in G; necessarily, K* contains a distinct representative for each of these maximum independent sets. The corresponding set K of vertices in G (the vertices whose expanded cliques in G* intersect K*) is a clique in G with the property that it intersects every maximum independent set in G. Therefore, the graph formed from G by removing K has clique cover number at most one less than the clique number of G, and independence number at least one less than the independence number of G, and the result follows by induction on this number.

Relation to the strong perfect graph theorem
The strong perfect graph theorem of states that a graph is perfect if and only if none of its induced subgraphs are cycles of odd length greater than or equal to five, or their complements. Because this characterization is unaffected by graph complementation, it immediately implies the weak perfect graph theorem.

Generalizations
proved that, if the edges of a complete graph are partitioned into three subgraphs in such a way that every three vertices induce a connected graph in one of the three subgraphs, and if two of the subgraphs are perfect, then the third subgraph is also perfect. The perfect graph theorem is the special case of this result when one of the three subgraphs is the empty graph.

title: Perfect graph theorem


text:
User talk:Hinatasou

Welcome to Wikipedia. I have noticed you created some articles on Animesou, a website. However, wikipedia policy says that unless it is a famous website, say slashdot or something similiar, it doesn't get a article. If you want something to do, here is a list:

Thanks for coming. Burgundavia 22:07, May 21, 2004 (UTC)

Recreating Animesou
Please stop recreating the article Animesou. It is an advertisement and the subject does not seem to be worthy of an article. If you do not cease and desist you will be blocked from editing for a time. Guanaco 22:27, 21 May 2004 (UTC)

No longer a candidate for speedy deletion
The article seems to have been improved somewhat and is no longer a candidate for speedy deletion. However, it will be listed on Votes for Deletion until a decision is made. Guanaco 22:29, 21 May 2004 (UTC)

From the User
Sorry Guanaco and Burgundavia. This is my first time and I thought there was some html error deleting the page which is why I kept recreating. I thought it would serve as a good resource in addition to the topics on anime and ADV Films.

authors: Template namespace initialisation script

title: User talk:Hinatasou