# Conjecture in graph coloring

Assume all graphs are simple and undirected (but perhaps disconnected).

We say that G is k-flexible if we can take an arbitrary stable set $$V'$$ of at most k vertices, give each $$v \in V'$$ vertex a distinct color, and color the other vertices so that the result is a proper k-vertex coloring. To illustrate: $$C_5, C_7$$ would thus be 3-flexible , but $$C_4$$ is not 2-flexible.

Conjecture: Let $$G = (V,E)$$ be a k-chromatic and k-flexible graph. now select up to $$k$$ arbitrary stable vertices in $$G$$ and connect every pair by an edge. The resulting graph $$G'$$ is then still k-chromatic (That's obvious). Furthermore , $$G'$$ is $$(k+1)-$$flexible

Or the following weaker conjecture: Let $$G = (V,E)$$ be a k-chromatic. We say a stable subset is flexible if we can color each vertex in it distinctly and still end up with a proper k-coloring. That is, if we draw edges between each vertex in a flexible set, the resulting graph is still k-chromatic. Let $$X,Y \subset V$$ be stable flexible subsets (of at most $$k$$ vertices) that have at most 1 vertex in common. If we draw edges for every pair $$(x',x'')$$in $$X$$ and $$(y',y'')$$ in $$Y$$ , then the resulting graph has a proper $$k+1$$-coloring

• The first conjecture seems obviously false, take $k$ disjoint vertices ...(plus you give a stricter requirement after your graph is more constrained. Commented Mar 27, 2023 at 6:15
• Maybe you misunderstood what I mean with k+1 flexible. The graph is more constraint but in turn I will allow suboptimal colorings. I allow a k+1 coloring on a graph that is k-colourable. Take any planar graph or map and you see hopefully it's a quite generous relaxation Commented Mar 27, 2023 at 11:27
• Triangle free planar graphs are 3-chromatic and I believe also 3 flexible, but they definitely have some level of flexibility. Draw one triangle in the graph. Now, blindly select 4 vertices and color them distinctly. It's a piece of cake to finish the 4-colouring. Commented Mar 27, 2023 at 11:34
• Yes, I'm dumb, a $k+1$ coloring is not a stricter requirement, I don't know what I was thinking Commented Mar 27, 2023 at 15:27

Take a graph composed of $$K_{2, 2}$$ and two disjoint vertices. It is clearly 3-colorable (if you really want 3-chromatic, add a disjoint triangle), and by closer inspection, it is 3-flexible. If you take a stable set that contains only one of the two isolated vertices (so the two other vertices are on the same sides of $$K_{2, 2}$$), it disproves the first conjecture.
To disprove the second conjecture, take a graph composed of $$K_{2, 2}$$ and one disjoint vertex. It is 3-colorable and 3-flexible. There are only two stable sets of 3 vertices, sharing only one vertex. Adding edges on these stable sets gives $$K_5$$, which is not 4-colorable.
• @BobLangefeld Sorry, I meant $K_{2, 2}$ Commented Mar 27, 2023 at 21:34
• Ah, I read it as $k$-coloring... I will get back at it Commented Mar 27, 2023 at 21:58