Draft:Selective Graph Coloring Problem
Submission declined on 8 June 2026 by Staraction (talk).
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
|  |
Comment: Entire lede is lifted from the source, word-for-word. Please rephrase in your own words. Staraction (talk · contribs) 13:25, 8 June 2026 (UTC)
The Selective Graph Coloring Problem (SGCP), also known as the Partition Coloring Problem (PCP), is a problem related to graph coloring. [1] [2] [3] [4] [5] [6] [7] [8]
Problem Definition
[edit]Given is an unweighted, undirected graph G =< V, E > with a set of nodes V and a set of edges E. Each node is assigned to one subgraph, a so-called cluster Ci. In total there are n disjoint clusters. The goal is to find a subgraph S = G(W) with W =< v1, ..., vn > where vi ∈ Ci, 1 ≤ i ≤ n. The subgraph should have a minimal chromatic number. The chromatic number is the minimal number of different colors using which the nodes of a graph can be colored so that there is no single pair of nodes u and v connected by an edge (u, v) that have the same color.
Thus, the SGCP is an extension of the graph coloring problem, which computer scientists and mathematicians have studied for decades. The Graph Coloring Problem is about computing the chromatic number of a given graph, and already in 1972 it was discovered to be an NP-equivalent problem. [9] Since the Graph Coloring Problem is a subproblem of the selective graph coloring problem, the selective graph coloring problem is NP-hard as well. For this reason it makes sense to use a heuristic approach both to estimate the chromatic number of a possible solution and to find a better solution.
References
[edit]- ↑ https://www.ac.tuwien.ac.at/files/pub/volko-13.pdf
- ↑ https://www.ac.tuwien.ac.at/files/pub/fritz_14.pdf
- ↑ "On some applications of the selective graph coloring problem". European Journal of Operational Research. 240 (2): 307–314. January 16, 2015. doi:10.1016/j.ejor.2014.05.011 – via www.sciencedirect.com.
- ↑ "(PDF) Selective Graph Coloring on Some Special Classes of Graphs".
- ↑ https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/2069-09.pdf
- ↑ Şeker, Oylum; Ekim, Tınaz; Taşkın, Z. Caner (June 8, 2019). "A decomposition approach to solve the selective graph coloring problem in some perfect graph families". Networks. 73 (2): 145–169. doi:10.1002/net.21850 – via Wiley Online Library.
- ↑ "An Exact Cutting Plane Algorithm to Solve the Selective Graph Coloring Problem in Perfect Graphs". DeepAI. November 29, 2018.
- ↑ https://folia.unifr.ch/rerodoc/324532/files/selective_rero_0.pdf
- ↑ R. Karp: Reducibility Among Combinatorial Problems. Complexity of Computer Computations, pages 85-103, 1972.
- We can only accept text if it is explicitly released under a compatible free license or is in the public domain.
- If the text is not freely licensed, you must rewrite or summarize it entirely in your own words. Changing a few words is still considered a copyright violation.
- If you own the text you cannot paste it here unless you formally release it via our release process.
Users who continue to post copyrighted material may be blocked from editing Wikipedia.