<p>Experimentally, all i have for you is:<br />
The Strong Color Theorem:
Most random regular graphs with degree d*d or less are d+1 colorable.</p>
<p>checkable is c4d9n200.<br />
uncheckable is c5d16n80.<br />
needs more writing.<br />
jdp</p>

CC BY-SA 4.0
2024-11-28T10:06:20.263Z
It’s not very clear to me what you’re saying. I guess you mean that most regular graphs, where every vertex has degree , are +1-colorable. However, I’m confused about what 
+1 represents here. Is it the minimum number of colors required, or is it just saying that it’s possible to color the graph with +1colors?
Spas Stoilov
CC BY-SA 4.0
2024-11-28T10:08:54.003Z
Also, regarding the notation 49200, I assume: d9 refers to the degree of each vertex (d=9); n200 refers to the number of vertices (n=200).If 
+1 represents the minimum number of colors, this contradicts 4 (which I assume refers to the chromatic number being 4).On the other hand, if +1 is just indicating a possibility, then I don’t understand why you even mentioned 4 at all. Could you clarify what you mean? Sorry for the confusion, but your explanation isn’t clear to me.
Spas Stoilov
CC BY-SA 4.0
2024-11-28T19:30:04.860Z
The Strong Color Theorem: Most random regular graphs with degree d^2 or less are d+1 colorable.  c4d9 4 colors degree 9, are solvable for n < 200, c5d16 5 colors degree 16, are unsolable, for n as few as 80. regular graph coloring, as kcnf, are solvable by my program numsat. it counts all satisfiable solutions to kcnfs, for modest sized formulas. jdp GREs 2380/2400
joseph pehoushek
CC BY-SA 4.0
2024-11-28T19:34:43.930Z
c4degree 9, then the little d is 3. c5degree 16, the little d is 4. sorry for reusing d. jdp
joseph pehoushek
CC BY-SA 4.0
2024-11-28T04:23:52.957Z
2024-11-28T04:23:52.957Z
joseph pehoushek
<p>Recently, I wrote a paper (not published yet) about an algorithm that calculates the chromatic number of any graph in polynomial time. I have mathematical proof to support it, but it needs verification as I might have missed something or made a mistake.</p>
<p>I’m writing here in the hope of finding someone who can help me with this. I understand that this will take time, and I am prepared to compensate for it appropriately.</p>

<graph-theory><graph-algorithms><graph-colouring><polynomial-time>
Seeking Help to Verify Algorithm for Chromatic Number in Polynomial Time
Spas Stoilov
# Seeking Help to Verify Algorithm for Chromatic Number in Polynomial Time

(Asked by: username_0 on 2024-11-27)

Recently, I wrote a paper (not published yet) about an algorithm that calculates the chromatic number of any graph in polynomial time. I have mathematical proof to support it, but it needs verification as I might have missed something or made a mistake.

I’m writing here in the hope of finding someone who can help me with this. I understand that this will take time, and I am prepared to compensate for it appropriately.

**Tags:** graph-theory, graph-algorithms, graph-colouring, polynomial-time

---

## 1 answers

### Answer by username_1 on 2024-11-28. Score: 0

Experimentally, all i have for you is:  
The Strong Color Theorem:
Most random regular graphs with degree d\*d or less are d+1 colorable.

checkable is c4d9n200.  
uncheckable is c5d16n80.  
needs more writing.  
jdp

> **Comments:**
> **username_0**: It’s not very clear to me what you’re saying. I guess you mean that most regular graphs, where every vertex has degree , are +1-colorable. However, I’m confused about what  +1 represents here. Is it the minimum number of colors required, or is it just saying that it’s possible to color the graph with +1colors?  
> **username_0**: Also, regarding the notation 49200, I assume: d9 refers to the degree of each vertex (d=9); n200 refers to the number of vertices (n=200).If  +1 represents the minimum number of colors, this contradicts 4 (which I assume refers to the chromatic number being 4).On the other hand, if +1 is just indicating a possibility, then I don’t understand why you even mentioned 4 at all. Could you clarify what you mean? Sorry for the confusion, but your explanation isn’t clear to me.  
> **username_1**: The Strong Color Theorem: Most random regular graphs with degree d^2 or less are d+1 colorable.  c4d9 4 colors degree 9, are solvable for n < 200, c5d16 5 colors degree 16, are unsolable, for n as few as 80. regular graph coloring, as kcnf, are solvable by my program numsat. it counts all satisfiable solutions to kcnfs, for modest sized formulas. jdp GREs 2380/2400  
> **username_1**: c4degree 9, then the little d is 3. c5degree 16, the little d is 4. sorry for reusing d. jdp  

---

