1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ The first conjecture seems obviously false, take $k$ disjoint vertices ...(plus you give a stricter requirement after your graph is more constrained. $\endgroup$
    – caduk
    Commented Mar 27, 2023 at 6:15
  • $\begingroup$ 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 $\endgroup$ Commented Mar 27, 2023 at 11:27
  • $\begingroup$ 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. $\endgroup$ Commented Mar 27, 2023 at 11:34
  • $\begingroup$ Yes, I'm dumb, a $k+1$ coloring is not a stricter requirement, I don't know what I was thinking $\endgroup$
    – caduk
    Commented Mar 27, 2023 at 15:27

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @BobLangefeld Sorry, I meant $K_{2, 2}$ $\endgroup$
    – caduk
    Commented Mar 27, 2023 at 21:34
  • $\begingroup$ OK I agree on the first point, but not on the second contradiction. we can color the result easily with 4 colors , as I conjectured $\endgroup$ Commented Mar 27, 2023 at 21:48
  • $\begingroup$ Ah, I read it as $k$-coloring... I will get back at it $\endgroup$
    – caduk
    Commented Mar 27, 2023 at 21:58
  • $\begingroup$ Ok, it should be good with this counter-example... $\endgroup$
    – caduk
    Commented Mar 27, 2023 at 22:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .