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 <math> 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 P^NP[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#Simplification and verification. —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\geq 1$ 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! :)

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

Graph coloring
Problem
Input	Graph $G$ with $n$ vertices. Integer $k$
Output	Does $G$ admit a proper vertex coloring with $k$ colors?
Algorithms
Running time	$O(2^{n}n)$
Complexity	NP-complete
Garey–Johnson	GT4

Chromatic number
Problem
Input	Graph $G$ with $n$ vertices.
Output	$\chi (G)$
Algorithms
Running time	$O(2^{n}n)$
Complexity	NP-hard
Garey–Johnson	GT4
Approximable	$O(n(\log n)^{-3}(\log \log n)^{2})$
Not approximable	$n^{1-\epsilon }$ unless P=NP

Chromatic polynomial
Problem
Input	Graph $G$ with $n$ vertices. Integer $k$
Output	The number $P(G,k)$ of proper $k$-colorings of $G$
Algorithms
Running time	$O(2^{n}n)$
Complexity	#P-complete
Approximable	FPRAS for restricted cases
Not approximable	No PTAS unless P=NP

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(kⁿ) 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)\,$

This should look like this:

$\chi (G)\leq \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.wiki.x.io/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 Wikipedia: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"

@David Eppstein: 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#Vertex_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)