Talk:Complete coloring

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

Read in section Algrithms

For any fixed k, it is possible to determine whether the achromatic number of a given graph is at least k, in linear time.

Read in article "The First-fit Chromatic and Achromatic Numbers" Stephanie Fuller, December 17, 2009, page 9:

Finding the achromatic number of a graph is NP-hard; determining whether it is greater than some number is NP-complete. This was proven in [24] using minimum edge dominating sets. In this paper, they also prove that even when limited to the complements of bipartite graphs, it is an NP-hard problem [24]

So, it is NP-complete or "linear time"? Jumpow (talk) 18:10, 17 April 2014 (UTC)JumpowReply

It is linear time for fixed k. It is NP-complete when k is a variable that is part of the input. —David Eppstein (talk) 18:28, 17 April 2014 (UTC)Reply

Don't understand....Loop though all k=0:N and find max k when for GIVEN GRAPH "achromatic number is at least k". Got O(N*N). Jumpow (talk) 16:55, 18 April 2014 (UTC)JumpowReply

Let's suppose, for the sake of specificity, that the running time, measured as a function of both ${\displaystyle k}$ and ${\displaystyle n}$, is ${\displaystyle O(3^{k}n)}$ (the actual dependence on ${\displaystyle k}$ from the cited source appears to be much worse). Then for any particular value of ${\displaystyle k}$, such as ${\displaystyle k=4}$, the ${\displaystyle 3^{k}}$ part of this bound is just a constant (81 for ${\displaystyle k=4}$) and can be removed from the ${\displaystyle O}$-notation. But if you are testing all values of ${\displaystyle k}$ from 1 to ${\displaystyle n}$ as in your "loop through all" statement, then the time is ${\displaystyle O(\sum _{i=1}^{n}3^{i}n)=O(3^{n}n)}$, much bigger than ${\displaystyle O(n^{2})}$. —David Eppstein (talk) 18:04, 18 April 2014 (UTC)Reply

I understood what is wrong a couple of hours ago... I did not count, that constant will depend from k, and dependency will not linear. But, I think, article need some crarifying. Thank you for patience and explanation. Jumpow (talk) 20:06, 18 April 2014 (UTC)JumpowReply

Hello fellow Wikipedians,

I have just modified one external link on Complete coloring. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20040707113436/http://www.maths.dundee.ac.uk/~kedwards/biblio.html to http://www.maths.dundee.ac.uk/~kedwards/biblio.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 18:57, 11 August 2017 (UTC)Reply