Strong Chromatic Numbers of Graphs with Maximum Degree 2

Lars-Daniel Öhman

Abstract. The strong chromatic number, χ_{s}(G), introduced by Alon, is the least integer k such that in whichever way we add disjoint cliques of order k to the vertex set of G, or, if k doesn’t divide |V (G)|, to G with an appropriate number of added isolated vertices, the chromatic number doesn’t rise above k. Alon conjectured that χ_{s}(G) ≤ 2Δ(G). If this upper bound is the correct one, this leaves room for only two values of χ_{s} for graphs with maximum degree 2, namely 3 ≤ χ_{s}(G) ≤ 4. We give a partial characterisation of which graphs with Δ(G) = 2 has χ_{s}(G) = 3 or 4. We present some computational evidence of a conjecture as to a full characterisation.

We also show that χ_{s}(G) = k implies that G with added m-cliques for m ≥ k has chromatic number m. This has often been attributed to Fellows, but his result is only for infinite graphs, where divisibility ceases to be an issue.

Finally, we propose a slightly different colouring parameter.

1. Introduction

The strong chromatic number χ_{s}(G) of a graph G is the smallest integer k such that G is strongly k-colorable. G is strongly k-colorable if any partition π of V (G) into parts of size k (a k-exact partition) allows an orthogonal partition (thus consisting of k sets) π^{⊥} with sets independent in G. Another equivalent formulation is obtained by adding disjoint kcliques on the same vertex set, and asking if the resulting graph is kcolorable, no matter how the cliques were added. Both formulations will be used in what follows. If k ∤ n = |V (G)|, we add k⌈n/k⌉ − n isolated vertices to G, to allow for a k-exact partition.

The parameter is well-defined, because χ_{s} ≤ n, trivially, and because of the fact that any non-empty set of positive integers has a greatest lower bound. That strong k-colorability implies strong (k + 1)-colorability is not absolutely trivial, and the usual source of reference for this claim is Fellows [2]. In that paper, however, the actual theorem is proven only for infinte graphs, where divisibility ceases to be a problem, in the sense that any infinite set allows both a k-exact and a (k + 1)-exact partition. Therefore, we prove that the monotonicity property holds in general for finite graphs, in Theorem 2.2 below.

Not much is known about χ_{s}. Trivially, χ_{s}(G) ≥ χ(G). All graphs with maximum degree 0 have strong chromatic number 1, all graphs with maximum degree 1 have strong chromatic number 2 (which can also be easily seen), but when the maximum degree is 2, no complete characterisation is known. For connected graphs with maximum degree 2, we give a complete characterization of the strong chromatic number in Section 3. We also know that χ_{s}(G) ≥ 3 for all graphs G with maximum degree 2. It cannot be 2, as we may connect the two neighbours of a 2-valent vertex with an edge (that is a K_{2}), making a triangle, which is not 2-colorable. In the same way, for any d and any graph with Δ(G) = d it also holds that χ_{s}(G) ≥ d + 1. To see this, we observe that we may place a d-clique on the neighbours of a d-valent vertex, creating a (d + 1)-clique, which is not d-colorable.

We follow Alon [1] in setting χ_{s}(d) = max{χ_{s}(G)}, where d is a positive integer, and the maximum is taken over all graphs G with maximum degree d. Fleischner and Stiebitz [4] give a family of graphs with maximum degree d, that are not strongly (2d−1)-colorable, thereby establishing χ_{s}(d) ≥ 2d. On the other hand, Haxell [5] has χ_{s}(d) ≤ 3d − 1. Also, if |V (G)| ≤ 6d, Johansson, Johansson and Markström [8] have χ_{s}(G) ≤ 2d.

2. Establishing when χ_{s}(G) = 3

When we investigate χ_{s}(d), we may restrict ourselves to d-regular graphs. This is so, because when we ask for the strong chromatic number of a graph G with Δ(G) = d, if G is not regular, we may instead instead ask for the strong chromatic number of the graph obtained by taking a suitable number of copies of G, and connecting low-degree vertices to produce a d-regular graph. The strong chromatic number may have gone up, but we are still in the class of graphs with maximum degree d.

Furthermore, we may assume that no added clique has any edge paralell to an edge already present in the graph: If the edge in G is e = {u, v}, we construct an auxiliary graph by making a copy of G, with all cliques present, where the copied edge is named f = {x, y}, and connect u to x, and v to y. We then remove the connection between u and v, and between x and y. Note that the added cliques still establish connections uv and xy. G has strong chromatic number less than or equal to that of the auxiliary graph, and the auxiliary graph is still in the class of d-regular graphs.

The following proposition can be found in [2], but we state it here with a new proof, in a more graph-theoretic formulation.

Proposition 2.1. Let G be a disjoint union of graphs on at most k vertices. Then χ_{s}(G) ≤ k.

Proof. We construct a bipartite graph B = (B_{1}, B_{2}) as follows: Let each component of G be a vertex in B_{1} and each added k-clique a vertex in B_{2}. Two vertices u ∈ B_{1} and v ∈ B_{2} are connected iff the component and the clique they represent share a vertex. Note that multiple edges are allowed. We see that Δ(B) ≤ k, and therefore B has an edge coloring using k colors. This edge coloring gives a coloring of the vertices in G, such that no two vertices in the same added clique or in the same connected component of G receive the same color. Thus, this coloring is proper with respect to the k-cliques added, and χ_{s}(G) ≤ k. □

The next theorem establishes that strong k-colourability is a monotone property, even for finite graphs.

Theorem 2.2. Let G be strongly k-colorable. Then G is strongly (k + 1)- colorable.

Proof. For ease of notation, we let H = G ∪ (k⌈n/k⌉ − n)K_{1}, |H| = mk = k⌈n/k⌉, where n = |V (G)|. Let ℓ be the smallest positive integer such that L = |V (G)| + ℓ is a multiple of k + 1. We distinguish three cases: L < mk, L = mk and L > mk. The case L = mk. This part is the method of proof from [2] (and the other parts are similar). Suppose we are given a (k + 1)-exact partition π of V (G) ∪ ℓK_{1} = V (G), and cliques are added to each C ∈ π.

Take any transversal T of π. If T were independent, we would be finished, for then we could let T be the color class c_{k+1}, and color the remaining graph with k colors (which is possible because the remaining graph is an induced subgraph of G, and therefore has lower strong chromatic number). Of this, however, we can not be sure. Instead, we observe that k divides |T |, so that T allows a k-exact partition, π_{T}. If we set C′ = C − T for each C ∈ π, then π′ = π_{T} ∪ {C′ : C ∈ π} is a k-exact partition, and there is an independent transversal T′ whose parts are the color classes in a proper k-coloring of G.

Let R = T′ ∩ (∪_{C∈π}C′). Then R is an independent transversal of π, and we are finished. The case L < mk. We know then that 0 ≤ ℓ < k. Let π be a (k +1)-exact partition of V (G)∪ℓK_{1}. Take any transversal T of π. Let π_{T} be a partition of T in parts of size k, with one part T_{p} of size p = k − (mk − n − ℓ), so that k = p + (mk − n − ℓ) = p + (|H| − |V (G)| − ℓ) = p + q, where q < k. We set C′ = C − T for each C ∈ π By adding q isolated vertices to G, and placing them in the part T_{p}, we create a k-exact partition π_{H} of V (H) consisting of the C′ and the parts of π_{T} with the part T_{p} extended to T′_{p}.

Take an independent transversal T_{H} of π_{H} where the vertex chosen from T′_{p} is not one of the q added ones. Such a transversal exist, since there in fact exist an orthogonal partition to π_{H}.

Let R = T_{H} ∩ (∪_{C∈π}). Then R is an independent transversal of π, and we are finished. The case L > mk. Take a (k + 1)-exact partition π of V (G) ∪ ℓK_{1}.

If |C ∩ (ℓK_{1} − (V (H) − V (G)))| = 1 for each C ∈ π, we proceed as follows: Let T be a transversal of π, containing all the vertices from F = ℓK_{1} − (V (H) − V (G)). We let π_{F} = {C ∈ π : C ∩ F ≠ ∅}. Partition T −F in parts of size k, and name this partition π_{T −F}. If we again set C′ = C − T for each C ∈ π, we have a k-exact partition π′ = π_{T −F} ∪ {∪_{C∈π}C′} of V (H). By assumption, π′ has an independent transversal T′. Then R = T′ ∩ {∪_{C∈π}C′} is an independent transversal of π, with R ⊂ V (G). If we set R′ = R−{∪_{C∈π_{F}} C}∪F, we still have an independent transversal to π. If we let R′ be the color class c_{k+1}, and remove these vertices, we retain an induced subgraph of H, and a k-exact partition π′′ = {C −R′ : C ∈ π}, that can be k-colored by assumption.

If |C ∩ F | ≥ 2 for some C ∈ π we proceed as follows: Observe that 0 < ℓ ≤ k. Let π_{F} be as above, and π_{2} be the C ∈ π_{F} with |C ∩ F | ≥ 2. Take a transversal T to π containing a vertex from each C ∩ F for each C ∈ π_{F}. We set C′ = C − T for each C ∈ π. Then π′ = {∪_{C∉π_{F}} C′} is a k-exact partition of an induced subgraph of G, and so there is an independent transversal T′ to π′.

Then R = T′ ∩ {∪_{C∉π_{F}} C} is an independent set in V (G), and R′ = R∪(F ∩T) is an independent transversal to π. We let R′ be the color class c_{k+1}. Removing R′, the number of remaining vertices is a multiple of k, so G′ = G ∪ ℓK_{1} − R′ can be regarded as a subgraph of H, where we pretend that the remaining vertices from F are vertices in H, with all incident edges removed. G′ is thus a spanning (containing all vertices) subgraph of an induced subgraph of H, and a k-exact partition π_{H} = {C −R′ : C ∈ π}, which by assumption allows a k-coloring. □

3. The connected case

As is well known, Fleischner and Stiebitz [3] have χ_{s}(C_{3n}) = 3. This is the so-called “cycle-plus-triangles” problem. For a proof from first principles (which contrary to popular belief does not seem to give an effective algorithm for actually finding a colouring) see [9]. Häggkvist and Johansson [6] have established that the exact same method of proof as in [3] will work for C_{3n+2}, i.e. “cycle-plus-triangles-plus-chord”, and thus χ_{s}(C_{3n+2}) = 3. Thus we also have (for n ≥ 1, of course) χ_{s}(P_{3n}) = χ_{s}(P_{3n+2}) = 3.

Two old examples where χ_{s} = 4 appear in the literature: One is a C_{4}, where we place opposite corners together in the partition, preventing a 3coloring. For C_{7}, an example attributed to H. Sachs (see [4]) is as follows: Connect vertices v_{1} and v_{3} by an edge, vertices v_{2}, v_{4} and v_{6} by a triangle, and vertices v_{5} and v_{7} by an edge. The single edges are then joined to one isolated extra vertex each, to produce triangles. This graph is not 3-colorable. According to Jensen and Toft [7], Huang noted in 1993 that all C_{3n+1} have strong chromatic number 4, but since the construction we present here can be used in other settings, we again prove that fact.

Proposition 3.1. χ_{s}(C_{3n+1}) = 4 for all n.

Proof. C_{4} is not strongly 3-colorable as observed above, by choosing crossing chords, so for n = 1, the proposition holds.

Suppose now that we have established the result for n = m. We choose two neighbouring vertices in C_{3m+1} with added triangles and chords, represented in Figure 1 by a triangle and a square vertex respectively, and insert a triangle between them, again as depicted in Figure 1. The resulting graph is a C_{3(m+1)+1} with added triangles, and if it is 3-colorable, then so was the original graph.

→

Figure 1. Inserting a triangle in a cycle Thus, by induction, we are finished. □

A more direct description of one of the possibilities of inserting triangles is the following:

For n ≥ 3, we construct a graph H_{3n+1} starting with a C_{3n+1}, with vertices numbered v_{1}, v_{2}, … v_{3n+1}, connecting v_{3i}, v_{3i+2} and v_{3i+4} as a triangle, for each 1 ≤ i ≤ n − 2. Additionally, make v_{2}, v_{4} and v_{3n} into a triangle, and connect v_{3n−1} to v_{3n+1}, and v_{3n−3} to v_{1}. To see that the resulting graph is not 3-colorable, we color the triangle i = 1 with colors a, b and c, in this order along the cycle. This immediately forces the colors on vertices v_{4} and v_{6}, and then the colors on vertices v_{2} and v_{8}, and by the way the triangles are interlaced, every color is forced. Each triangle will have the colors a, b, c in that order along the cycle. In the end, the colors forced on the two single edges will conflict.

Figure 2. H_{10} and H_{13}

In fact, the family of 4-chromatic graphs constructed in the proof is also 4-critical: If either end of one of the two chords is removed, our ground for conflict is neutralized, and we can make do with 3 colors. The same holds for the removal of any vertex in the neighborhood of the chords. Finally, if the chain of interlacing triangles is broken, we see that we gain enough freedom that the order of the colors may be changed to avoid conflict on the two chords.

Another family of examples, with crossing chords, may be directly constructed as follows.

For each n ≥ 3 we construct a graph X_{k,l}, where k, l ≥ 1, k + l + 1 = n from a cycle on 3n + 1 vertices: Make vertices v_{2}, v_{3n+1} and v_{3n−1} a triangle. For 1 ≤ i ≤ k make vertices v_{3i}, v_{3i+2} and v_{3i+4} a triangle. For 1 ≤ j ≤ l make vertices v_{3(k+j)+2}, v_{3(k+j)+4} and v_{3(k+j)+6} a triangle, where the last vertex in the triangle j = l will be v_{3(k+l)+6} = v_{3(n−1)+6} = v_{3n+3}, which, indices taken modulo 3n + 1 is the vertex v_{2}. Finally, add the chords from vertex v_{1} to v_{3i+3} and from vertex v_{3i+6} to v_{4}. Observe that

Figure 3. X_{1,1}, X_{2,1} and X_{2,2}

for any k, l, the chords cross, and that for n = 3, they are crossed by an even number (2, that is) of triangle edges. For k = 1, l ≠ 1 the two chords are crossed only by the triangle i = 1. For k, l ∈ {1, 2} the graphs are shown in figure 3. Observe that X_{k,l} is isomorphic to X_{l,k}.

This family of graphs is 4-chromatic: Without loss of generality, we color the triangle i = 1 with colors a, b and c in that order along the cycle. This immediately forces the colors on all vertices v_{3} … v_{3k+4} by the way the triangles are interlaced. Can we finish this coloring? We observe that the color a may not be used on vertices v_{1} or v_{2}, and that the color c may not be used on vertices v_{3k+5} or v_{3k+6}. We draw the conclusion that color a must be used on vertex v_{3n+1}, and that the color c must be used on vertex v_{3k+7}. Continuing in ths fashion, we see that for 1 ≤ j ≤ l all vertices v_{3(k+j)+1} must receive the color c, and so, we have a conflict on vertex v_{3n+1}, where we must use color c, and we must use color a.

This family of graphs is also 4-critical: If we remove any of the endpoints of the chords, the resulting graph is 3-chromatic, as can be easily checked. If one of the chains of interlacing triangles is broken, we gain enough freedom at this point to change the order of the colors along the large cycle, thereby eliminating the conflict described above.

Instead of this specific description of counterexamples for each n, we may start from the example on 4 vertices, and by means of a small gadget succesively add triangles to create examples for any n. One example of such a gadget is the following.

Choose two adjacent vertices on the C_{3n+1}, and place the vertices of a new triangle to the left of, between and to the right of these two neighboring vertices, adding 3 new vertices to the cycle. Next, let the two initial neighboring vertices switch places. It may be easily verified that if the resulting graph is 3-chromatic, then so was the graph we started with.

Depending on where this gadget is applied, we may get different (nonisomorphic) examples. Also, other gadgets than this are conceivable.

For n = 1, 2 the examples described above are unique, which we have verified by computer. For n = 3, there are non-isomorphic examples of a cycle on 10 vertices, with two chords and two triangles added, all vertex disjoint, that have chromatic number 4.

The question remains whether χ_{s}(P_{3n+1}) equals 3 or 4. We resolve the question by considering the following construction.

Take two copies of the path, and connect the ends, yielding a cycle on 6n + 2 vertices. By the above, this cycle has strong chromatic number 3, and as each subgraph will have lower strong chromatic number, we have χ_{s}(P_{3n+1}) = 3.

4. The 2-regular case

By Proposition 2.1, a disjoint union of triangles has χ_{s} = 3. By Proposition 3.1, any disjoint union of cycles where some cycle has length 3n + 1 has χ_{s} ≥ 4.

By the following examples, any disjoint union G of cycles containing both a C_{3m}, m ≥ 1 and a C_{3n}, n ≥ 2 has χ_{s} ≥ 4. The construction is as follows:

The most basic example is C_{3} ∪ C_{6}. Place chords in the C_{6} between opposite vertices. Complete these chords to triangles by connecting both ends to a vertex in the C_{3}. The resulting graph is 4-chromatic, as can be easily checked. The properties of this graph we wish to generalise to longer cycles is that three vertices in the one cycle (here the C_{3}) are forced to have distinct colors, and three pairs of vertices in the other cycle (here the C_{6}) cannot tolerate having all distinct pairs of colors. This graph is shown in Figure 4.

To force colors a, b and c on three special vertices of a C_{3m}, m ≥ 1 is quite easy: For each 1 ≤ i ≤ m − 1 make vertices 3i, 3i + 2 and 3i + 4 a triangle. This leaves vertices 2, 4 and 3m, and by the way the triangles are interlaced, these vertices necessarily all have distinct colors.

In the other cycle, C_{3n} we proceed as follows. For 1 ≤ j ≤ n − 3, let vertices 3j, 3j+2 and 3j+4 form a triangle. Further, make vertices 3n−6, 3n − 4 and 3n a triangle. The remaining six vertices are connected with chords 3n − 3 to 4, 3n − 2 to 1 and 3n − 1 to 2. Without loss of generality, we may color the vertices of the triangle j = 1 with colors a, b and c, in that order along the cycle. The interlaced triangles are then forced to

Figure 4. H_{3,6} = C_{3} ∪ C_{6}

have the same sequence of colors on their vertices along the cycle. Also, vertex 4 gets the color b, and therefore the other end of the chord from 4 to 3n−3 gets color a. Two chords are left, where the colors are not forced. The graph induced by G on the vertices of these two chords is a C_{4}, and one pair of opposite vertices must not have color a, and the other pair of opposite vertices must not have color c. We can obviously not color this graph using the color b twice and each of a and c once. Therefore, the chords in the C_{3n} can not be connected to the free vertices in the C_{3m}, so as to form triangles, without forcing a conflict in any 3-coloring.

For C_{3} ∪ C_{6}, the example is unique, but for (n, m) = (3, 9) or (m, n) = (6, 6) there are two non-isomorphic examples. For C_{6} ∪ C_{6}, if we number the vertices in the two cycles 1, 2, 3, 4, 5, 6 and 7, 8, 9, 10, 11, 12, the two examples are given by {{1, 4, 6}, {2, 6, 10}, {3, 8, 11}, {5, 9, 12}} and {{1, 4, 7}, {2, 6, 9}, {3, 5, 11}, {8, 10, 12}}.

For C_{3}∪C_{9} where the C_{3} is indexed with 1, 2, 3, the two non-isomorphic examples are given by partitions {{1, 3, 5}, {2, 7, 10}, {4, 8, 11}, {6, 9, 12}} and {{1, 3, 7}, {2, 4, 10}, {5, 8, 11}, {6, 9, 12}}.

All these examples may be produced from the example with C_{3} ∪ C_{6} by use of the gadget described in Section 3.

Examples originating from Gallai (see [4]) show that the presence of three even cycles of equal length, or the presence of both a C_{2m+1} and a C_{4m+2} also gives χ_{s} ≥ 4. The example for three even cycles C_{2j} of equal length is simply C_{2j} × C_{3}, the cartesian product, namely where the C_{3}:s are all paralell, and cross each C_{2j} in one point each. For a C_{2m+1} and a C_{4m+2}, we may connect each diameter (chord connecting two vertices at maximum distance from each other) of the longer cycle, in order, with a single vertex from the shorter cycle, forming superpositioned triangles. The resulting graph is 4-chromatic.

These examples may be exploited first to show that χ_{s}(C_{3m+2} ∪C_{3n+2} ∪ C_{3k+2}) ≥ 4 for all m, n, k ≥ 2. The idea is to extend one C_{3m+2} by three vertices. We do this by giving two neighboring vertices in one of the C_{2j} in C_{2j} × C_{3} the names v_{2} and v_{4}. Now, around these, on the C_{2j}, in the order of the integers, we introduce vertices v_{1}, v_{3} and v_{5} and connect them as a triangle. We also switch the positions of vertices v_{2} and v_{4}. If there existed a 3-coloring of this graph, vertices v_{1} and v_{4} would necessarily have the same color a, and the same goes for the pair v_{2} and v_{5} and some color b ≠ a. Then we could remove vertices v_{1}, v_{3} and v_{5}, and switch back vertices v_{2} and v_{4}. The resulting graph would be isomorphic to C_{2j} × C_{3}, and be properly 3-colored, which is a contradiction to χ(C_{2j} × C_{3}) = 4. This is again the gadget of Section 3.

The smallest m for which 3m + 2 is even, and χ(C_{3m+2} × C_{3}) = 4 is m = 2, giving 3m + 2 = 8, so this construction is valid for 3C_{3m+2} for any m ≥ 2. Hence, we have shown the following proposition.

Proposition 4.1. For all m, n, k ≥ 2, it holds that χ_{s}(C_{3m+2} ∪ C_{3n+2} ∪ C_{3k+2}) ≥ 4.

At least our case analysis is reduced to the two parametrised questions of the value of χ_{s}(kC_{3} ∪mC_{5} ∪C_{3i+2} ∪C_{3j+2}) where i, j ≥ 2 and k, m ≥ 0, and χ_{s}(mC_{5} ∪ C_{3j+2} ∪ C_{3j+2} ∪ C_{3n}) where i, j, n ≥ 2 and m ≥ 0.

To support our conjecturing, a verification by computer, checking all possible partitions of the vertex set of G into sets of size 3 (with added isolated vertices to make |V (G)| divisible by 3) gives us the information in Table 1.

G  χ_{s}(G) G  χ_{s}(G) G  χ_{s}(G)
C_{3} ∪ C_{11}  3  C_{3} ∪ C_{3} ∪ C_{8}  3  3C_{3} ∪ C_{5}  3
C_{5} ∪ C_{6}  3  C_{3} ∪ C_{5} ∪ C_{5}  3
C_{5} ∪ C_{8}  3  C_{5} ∪ C_{5} ∪ C_{5}  3
C_{5} ∪ C_{9}  3
C_{6} ∪ C_{8}  3
C_{8} ∪ C_{8}  3

Table 1. Some strongly 3-chromatic 2-regular graphs

With this admittedly somewhat weak evidence at hand, we present the following conjecture, which is sharp if it holds true.

Conjecture 4.2. For all i, j ≥ 2 and k, m ≥ 0 it holds that

χ_{s}(kC_{3} ∪ mC_{5} ∪ C_{3i+2} ∪ C_{3j+2}) = 3,

and for all i, j, n ≥ 2 and m ≥ 0 it holds that

χ_{s}(mC_{5} ∪ C_{3i+2} ∪ C_{3j+2} ∪ C_{3n}) = 3.

A special case which may be a good starting point, is the conjecture that any disjoint union of C_{3}:s and C_{5}:s has strong chromatic number 3.

5. The general case

For starters, any disjoint union of paths has χ_{s} = 3. Why? Because we may add a short path (possibly raising the strong chromatic number) to ensure that |V (G)| = 3n, and then we can connect all the paths into a cycle (possibly raising the strong chromatic number), which has strong chromatic number 3, by the cycle-plus-triangles theorem.

A disjoint union of triangles and paths on at most 3 vertices has strong chromatic number 3, by Proposition 2.1. The question whose negative answer would give a complete solution to this problem is the following.

Given a graph G with χ_{s}(G) = 3, so that Δ(G) = 2, can it be that χ_{s}(G ∪ P_{m}) = 4 for some m? We need only consider the addition of one path, for instead of adding multiple paths, we may add a long path with the same number of vertices as the multiple paths put together. This long path clearly has a greater chance of raising the strong chromatic number. Also, a longer path is clearly a worse problem than a shorter one. Again, a computer verification gives the information in Table 2.

G  χ_{s}(G) G  χ_{s}(G) G  χ_{s}(G)
C_{3} ∪ P_{12}  3  C_{3} ∪ C_{3} ∪ P_{9}  3  3C_{3} ∪ P_{6}  3
C_{5} ∪ P_{10}  3  C_{3} ∪ C_{5} ∪ P_{7}  3  2C_{3} ∪ C_{5} ∪ P_{4}  3
C_{6} ∪ P_{9}  3
C_{8} ∪ P_{7}  3
C_{9} ∪ P_{6}  3
C_{11} ∪ P_{4}  3

Table 2. Some strongly 3-chromatic graphs

Conjecture 5.1. If the graph G has strong chromatic number 3, then so does the disjoint union G ∪ P_{n} for any n.

6. Alternative formulations

If χ_{s}(G) = k, is it also true that no matter how we add cliques on at most k vertices to the graph G ∪ (k⌈n/k⌉ − n)K_{1}, the resulting graph has chromatic number k? In particular, is there a graph on 3n or 3n + 1 vertices, that has a decomposition into a Hamilton cycle and a disjoint union of triangles and single edges, and has chromatic number 4?

What if we add cliques on at most k vertices only to the graph G, without additional isolated vertices? In fact, these two variations are the same.

Proposition 6.1. If the graph G with superimposed cliques of size at most k is k-chromatic then so is the graph G ∪ mK_{1} for each m ≥ 0.

Proof. For m = 0 this is trivial. If we remove a single isolated K_{1}, we lower m by one, and we reduce a clique by one. We now have the graph G ∪ (m − 1)K_{1} with superimposed cliques on at most k vertices, which we may color with k colors. The removed vertex has at most k−1 neighbours, and we may complete the coloring properly. □

We dub this property (in any of its equivalent formulations) strongly k^{≤}- colorable, and write χ_{s}^{≤}(G). For this parameter, monotonicity holds too, and that this is easier to prove should come as no surprise, considering how well-suited this parameter is to an inductive scheme. If k is the smallest integer such that G is strongly k^{≤}-colorable, we say that G is strongly k^{≤}-chromatic.

Proposition 6.2. Let G be strongly k^{≤}-colorable. Then G is strongly (k + 1)^{≤}-colorable.

Proof. Let π be a partition of V (G) with parts of size at most (k + 1). Further, let π_{k+1} be the parts with exactly (k + 1) elements. Of course, π_{k+1} may be empty, in which case we have nothing to prove. If we can find an independent set R of vertices in G that is a transversal to π_{k+1} we may let this transversal be the color class given color c_{k+1} and proceed to color the remaining graph, which is now partitioned in parts of size at most k, with k colors. This is possible, because the remaining graph is an induced subgraph of G.

Let T be any transversal to π_{k+1}, and for C ∈ π set C′ = C − T. Let π_{T} be a partition of T with parts of size at most k (possibly empty, or consisting of a single part). Then π′ = π_{T} ∪ {C′ : C ∈ π_{k+1}} is a partition of V (G) with parts of size at most k. By assumption, this partition has an independent transversal, T′, that contains elements from each class of size k, including, but not limited to, all classes previously of size (k + 1). Setting R = T′ ∩ (∪_{C∈π}C′), we see that R is an independent set in G, because T′ is independent, and that R is a transversal to π_{k+1}. The rest of the orthogonal partition may be found by the induction hypothesis. □

It may appear that strong k^{≤}-chromaticity is strictly stronger than strong k-chromaticity, but the added flexibility in assigning the dependencies is countered by the fact that there are less of them. For example, two triangles added to 6 vertices on a cycle contain 6 edges, whereas the three edges we may add to 6 vertices, though more flexibly so, contain only three edges.

Any G with Δ(G) = 0 is trivially 1^{≤}-chromatic, and Δ(G) = 1 implies 2^{≤}-chromaticity, as is also the case with χ_{s}. Also, we can mimic the proof of Proposition 2.1 for the parameter χ_{s}^{≤}, so that if G is a disjoint union of components with at most k vertices, then χ_{s}^{≤}(G) = k.

Proposition 6.3. Let χ_{s}(d) = k. Then χ_{s}^{≤}(d) = k.

Proof. Obviously, strong k^{≤}-chromaticity implies strong k-chromaticity. Also, if χ_{s}(d) = k, then every graph G with maximum degree d is strongly k^{≤}-colorable. To see this, place the cliques on at most k vertices on G, and add isolated vertices to G and interpret them as parts of the cliques that do not have k vertices, so as to ensure that all cliques have uniform size k. The resulting graph G still has maximum degree d, and so is strongly k-colorable. Therefore, the original G is strongly k^{≤}-colorable. □

Corollary 6.4. Let G be a disjoint union of paths and cycles. Then, provided χ_{s}(2) = 4, it holds that χ_{s}^{≤}(G) ≤ 4.

If we do not care to apply Corollary 6.4, we may in a fashion similar to Proposition ?? prove that any disjoint collection G of even cycles, any paths and a number of C_{3} has χ_{s}^{≤}(G) ≤ 4 (the only difference being that M is not a perfect matching, which in effect makes the coloring f more flexible), and in general we expect the two parameters χ_{s} and χ_{s}^{≤} to be the same for all graphs.

A counter example to the following conjecture would indeed be interesting. For example, is there a graph on 3n vertices that has a decomposition into a Hamiltonian cycle and disjoint triangles and edges, with chromatic number 4? If there are no triangles, the chromatic number is 3 by Brooks’ theorem, and if there are at most n triangles and edges, the cycle plus triangles theorem can be applied to prove that the chromatic number is 3. A computer verfication gives, for instance, that a C_{12} with at most 3 chords and some triangles has chromatic number 3.

Conjecture 6.5. Let G be a graph with χ_{s}(G) = k. Then the graph G ∪ mkK_{1} is strongly k-chromatic for each m ∈ ℕ. In other words, χ_{s}(G) = χ_{s}^{≤}(G) for any G.

The real formulation of the parameter should be something like

Definition 6.6. We say that the graph G is stable k-colorable if any graph obtained from G by adding disjoint graphs with maximum degree less than or equal to (k − 1) to the vertex set of G is k-chromatic. If k is the smallest integer such that G is stable k-colorable, we say that G is stable k-chromatic, and write χ^{s}(G) = k.

Stable k-chromaticity trivially implies strong k^{≤}-chromaticity. Again, if the graphs added are not all cliques, we gain in flexibility, but may lose in density, though not always strictly.

The proof of monotonicity proceeds along the lines of proposition 6.2. Also, whether the ground set is G or G ∪ (k⌈n/k⌉ − n)K_{1} is immaterial. Loosely stated, then, k is the minimum number that guarantees we can color the graph with k colors, even if new edges are added, only not more than k − 1 of them at each vertex. In other words, k colors can handle some limited changes to the graph, and is therefore a fitting chromatic number for graphs that are not eternally fixed.

For d = Δ(G) = 0, 1 we have, respectively, χ_{s}(G) = 1 = χ^{s}(G) and χ_{s}(G) = 2 = χ^{s}(G). Perhaps unfortunately, stable and strong chromaticity are not the same, as the following example (where d = 2) shows:

Take the graph G consisting of three disjoint triangles. By the above, χ_{s}(G) = 3, but by adding a C_{7} to this graph, we may produce Sachs’s example mentioned above, which has chromatic number 4, so χ^{s}(G) ≥ 4. In fact, any 2-regular graph with strong chromatic number 4 can be used to produce counter examples in the same way. It may be interesting, though probably hard, to study this parameter.

7. Open problems

(1) Let G be a graph with χ_{s}(G) = k on n = |V (G)| vertices. Is the graph H = G∪(k⌈n/k⌉−n+mk)K_{1} strongly k-chromatic for any m ∈ ℕ? This question is equivalent to the question of whether G is strongly k^{≤}-chromatic.

(2) Given a graph G with χ_{s}(G) = 3, so that Δ(G) = 2, can it be that χ_{s}(G ∪ P_{m}) = 4 for some m? A negative resolution of this question would imply the truth of Problem 1 for d = 2.

References

[1] N. Alon, The Strong Chromatic Number of a Graph, Random Struct. Alg. 3 (1992), no. 1 pp. 1–7.

[2] M. R. Fellows, Transversals of Vertex Partitions in Graphs, SIAM J. Disc. Math. 3 (1990), no. 2 pp. 206–215.

[3] H. Fleischner, M. Stiebitz, A Solution to a Colouring Problem of P. Erdős, Discrete Math. 101 (1992), pp. 39–48.

[4] H. Fleischner, M. Stiebitz, Some Remarks on the Cycle Plus Triangles Problem, The Mathematics of Paul Erdős II, Algorithms Combin. 14 (1997), pp. 136–142.

[5] P.E. Haxell, On the Strong Chromatic Number, Comb. Prob. Comp. 6 (2004), pp. 857-865.

[6] R. Häggkvist & Robert Johansson, personal communication.

[7] T. R. Jensen, B. Toft, Graph coloring problems, Wiley-Interscience (1995).

[8] A. Johansson, R. Johansson & K. Markström, Factors of r-partite Graphs, Research Report, no. 4 (2002), Dept. of Math., Umeå University.

[9] H. Sachs, Elementary Proof of the Cycle-Plus-Triangles Theorem, Combinatorics, Paul Erdős is Eighty (1993), pp. 347–359.

  E-mail address: lars-daniel.ohman@math.umu.se

Department of mathematics and mathematical statistics Umeå university, SE-901 87, Umeå, Sweden