# Acyclic colourings of graphs with bounded degree.

1 Introduction and notationAll graphs, which we consider, are finite and simple. For a graph G we denote its vertex set by V(G) and its edge set by E(G). The set of neighbours of a vertex v [member of] V(G) is denoted by [N.sub.G](v), or briefly by N(v). Let [DELTA](G) denote maximum degree of G. Let W [subset or equal to] E(G). We denote by G[W] the subgraph of G induced by the set W.

For any k [greater than or equal to] 0, we denote by Sk the class of all graphs of maximum degree at most k. Furthermore, we say that a graph G is subcubic if G [member of] [S.sub.3]. Let [D.sub.1] denote the class of all acyclic graphs.

A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, ..., k} of colours. We can also regard a k-colouring of G as a partition of the set V(G) into colour classes [V.sub.1], ..., [V.sub.k] such that each [V.sub.i] is the set of vertices coloured with i.

Let [P.sub.1], [P.sub.2], ..., [P.sub.k] be nonempty classes of graphs. A k-colouring of a graph G is called a ([P.sub.1], [P.sub.2], ...,

[P.sub.k])-colouring of G if for every colour 1 [less than or equal to] i [less than or equal to] k the subgraph induced in G by the colour class [V.sub.i] belongs to [P.sub.i]. Such a colouring is called an acyclic ([P.sub.1], [P.sub.2], ..., [P.sub.k])-colouring, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with colour i and a vertex coloured with colour j is acyclic. In other words, every bichromatic cycle in G contains at least one monochromatic edge. A bichromatic cycle (path) having no monochromatic edge will be called an alternating cycle (path).

The acyclic ([P.sub.1], [P.sub.2], ..., [P.sub.k])-colouring is called an acyclic k-colouring if for each i, 1 [less than or equal to] i [less than or equal to] k, the class [P.sub.i] is the set of all edgeless graphs. The minimum k such that G has an acyclic k-colouring is called the acyclic chromatic number of G, denoted by [X.sub.a](G).

The acyclic chromatic number and acyclic k-colouring have been investigated by many authors. In [7] Griinbaum showed that the acyclic chromatic number of any subcubic graph is at most 4. In [9] a linear time algorithm that uses at most 4 colours to acyclically colour vertices of such graph is presented. Burstein [4] proved that the acyclic chromatic number of graphs of maximum degree 4 is at most 5. In 1978 Kostochka [8] proved that it is an NP-complete problem to decide for a given graph G if [x.sub.a] (G) [less than or equal to] 3. Acyclic colourings of planar graphs, outerplanar graphs and graphs of maximum degree 5 were considered, see [2], [3], [5].

Boiron et al. studied the problem of acyclic ([P.sub.1], ..., [P.sub.k]) -colourings of graphs. In [1] they proved that a subcubic graph G has an acyclic ([D.sub.1], [S.sub.2])-colouring as well as an acyclic ([S.sub.1], [S.sub.1], [S.sub.1])-colouring. They also proved that any such G has an acyclic [D.sub.1], [D.sub.1])-colouring, provided G is neither [K.sub.3,3] nor [K.sub.4]. In the same paper it was conjectured that any subcubic graph has an acyclic ([S.sub.2], [S.sub.2])-colouring. In Section 2 we verify this conjecture to be true. Moreover, this conjecture cannot be generalized for an arbitrary k, what shows the following theorem:

Theorem 1 Let k [greater than or equal to] 4. Then there exists a graph with maximum degree k which has no acyclic ([S.sub.k-1], [S.sub.k-1])-colouring.

Proof: Let us consider a graph G = [C.sub.k] + [D.sub.k-2], where [D.sub.n] denotes a graph without edges of order n and '+' stands for the join operation. Obviously, G [member of] [S.sub.k].

Let us assume, to the contrary, that c is an acyclic ([S.sub.k-1], [S.sub.k-1])-colouring of G.

First observe, that if there is a pair of vertices x, y [member of] V([C.sub.k]) such that x and y have the same colour, say colour 1, then at most one vertex a [member of] V([D.sub.k-2]) can have colour 2, since c is acyclic. Similarly, if for a pair of vertices x', y' [member of] V([D.sub.k-2]) we have c(x') = c(y'), then at most one vertex from V([C.sub.k]) can have the colour different from c(x'). Therefore, if k > 4 then all vertices of [C.sub.k], except at most one, say z, must have the same colour, for example colour 1, and all vertices of [D.sub.k-2], except at most one, say z', also must have colour 1. One can observe that at least one of the vertices z, z' also must have colour 1, to avoid alternating cycles of length four. But in this case there is a vertex v such that v and its k neighbours have the same colour, a contradiction.

In the case k = 4 it is easy to verify that if two vertices of [C.sub.4] have colour 1 and another two have colour 2, then one vertex of [D.sub.2] must have colour 1 and another one colour 2, to avoid alternating cycles of length four, but then we obtain an alternating cycle of length six, a contradiction.

On the other hand, if all the vertices of [C.sub.4], except exactly one, have colour 1, then all the vertices of [D.sub.2] must have colour 1, to avoid alternating cycles, but then there is a vertex z [member of] V([C.sub.4]) which has colour 1 and all of its four neighbours also have colour 1, a contradiction.

In the remaining case, if all vertices of [C.sub.4] have colour 1, then at least one vertex of [D.sub.2] also must have colour 1, to avoid an alternating cycle, but this vertex has four neighbours in colour 1, a contradiction. [there does not exist]

The remainder of this paper is organised as follows. In the next section we show that any subcubic graph has an acyclic ([S.sub.2], [S.sub.2])-colouring. In Section 3 we present a polynomial-time algorithm which produces an acyclic ([S.sub.2], [S.sub.2]) -colouring of any cubic graph. In Section 4 we prove that it is an NP-complete problem to decide if a given graph G [member of] [S.sub.4] has an acyclic ([S.sub.2], [S.sub.2])-colouring.

2 Acyclic ([S.sub.2], [S.sub.2])-colourings of subcubic graphs

In this section we prove the following theorem:

Theorem 2 For any subcubic graph there is an acyclic ([S.sub.2], [S.sub.2])-colouring.

We start with the following straightforward Lemma:

Lemma 1 If G [member of] [S.sub.3] then G has an ([S.sub.2], [S.sub.2])-colouring.

Remark 1 Every subcubic graph has also an ([S.sub.1], [S.sub.1]-colouring. Any 2-colouring of G with the maximum number of bichromatic edges is an ([S.sub.1], [S.sub.1]-colouring of G.

First we prove that any cubic graph has an acyclic ([S.sub.2], [S.sub.2])-colouring. Let us consider a cubic graph G and its ([S.sub.2], [S.sub.2])-colouring. If this colouring is not an acyclic ([S.sub.2], [S.sub.2])-colouring, then there are vertices coloured such that they form an alternating cycle. We describe an algorithm which for a given alternating cycle C recolours vertices of G such that we obtain an ([S.sub.2], [S.sub.2])-colouring in which vertices of C do not form any alternating cycle and no new alternating cycle appears.

Let G be an ([S.sub.2], [S.sub.2])-coloured cubic graph and let C be an alternating cycle. Let v [member of] V(C). If we change the colour of v, then C is not alternating. Now the graph G has fewer alternating cycles, because v has two vertices coloured with the same colour as it has, then there is no new alternating cycle, but we could create a monochromatic [K.sub.1,3]. If we change the colour of its centre, then no new monochromatic [K.sub.1,3] appears, but in this case an alternating cycle could be formed. In our algorithm we destroy one forbidden structure and if our recolouring causes a creation of a new forbidden structure, then it will be destroyed in the next step.

First we describe the structures which can appear if we recolour vertices. Every forbidden structure is a coloured subgraph of cubic graph with two distinguished vertices: a root and a pre-root. The pre-root is the vertex whose colour will be changed.

Forbidden Structures

Structure (1) A monochromatic K1j3 with the centre y which satisfies the following: let N(y) = {[x.sub.1], [x.sub.2], z}, the vertices [x.sub.1] and [x.sub.2] are connected by an alternating path and the vertex z has at least one neighbour coloured with colour other than c(z). The root of the structure is the vertex y and the pre-root is the vertex [x.sub.1] or [x.sub.2].

Structure (2) A monochromatic [K.sub.1,3] with the centre x which satisfies the following: there is a vertex y [member of] N(x) such that y has exactly one neighbour z coloured with a colour other than c(y). Moreover, z has two neighbours coloured with colour c(z). The root of the structure is the vertex y and the pre-root is the vertex x.

Structure (3) Two monochromatic subgraphs [K.sub.1,3] one with the centre x the other with the centre y such that x [not equal to] y and the vertices x and y are adjacent. Moreover, there are two vertices [z.sub.1], [z.sub.2] [member of] N(y) \ {x} which are connected by an alternating path. The root of the structure is the vertex y and the pre-root is the vertex x.

Structure (4) The set of alternating cycles [C.sub.1], [C.sub.2], ..., [C.sub.k] such that {[x.sub.1], y, [x.sub.2]} [subset or equal to] V([C.sub.1]) [intersection] V([C.sub.2]) [intersection] * * * [intersection] V([C.sub.k]) and [x.sub.1], y, [x.sub.2] are three successive vertices of the cycles. The root of the structure is the vertex y and the pre-root is the vertex [x.sub.1] if it has a neighbour coloured with c([x.sub.1]) outside the cycle, otherwise the pre-root is the vertex [x.sub.2].

[FIGURE 1 OMITTED]

Observation 1 Let G be a cubic graph whose vertices are coloured with two colours.

1. Suppose that the 2-colouring of G satisfies the following:

(i) there is exactly one vertex y which has all neighbours coloured with the same colour as y and there is no other monochromatic [K.sub.1,3] and

(ii) the vertex y is a root ofStructure (1).

Let x be the pre-root ofStructure (1) which has the root at y. Then after recolouring x either there is no alternating cycle containing x and there is no monochromatic [K.sub.1,3] in G or there is exactly one monochromatic [K.sub.1,3], which has the centre at x and forms Structure (2) with the root at the vertex x.

2. Suppose that the 2-colouring of G satisfies the following:

(i) there is exactly one vertex x which has all neighbours coloured with the same colour and there is no other monochromatic [K.sub.1,3] and

(ii) the vertex x is a pre-root ofStructure (2).

Let y be the root ofStructure (2) which has the pre-root at x. Then after recolouring x there is no monochromatic [K.sub.1,3] in G. Moreover, if new alternating cycles appear, then they form Structure (4) with the root at the vertex x and the vertex y is not contained in any of them.

3. Suppose that the 2-colouring of G satisfies the following:

(i) there are exactly two monochromatic [K.sub.1,3], one with the centre in the vertex x and the other with the centre at the vertex y and

(ii) the vertex x is a pre-root and the vertex y is a root of Structure (3).

Then after recolouring the pre-root x of this Structure (3) there is no monochromatic [K.sub.1,3] in G. Moreover, if new alternating cycles appear then they form Structure (4) with the root at the vertex x and none of them contains the vertex y.

Observation 2 Let G be a cubic graph whose vertices are ([S.sub.2], [S.sub.2])-coloured. Let C be an alternating cycle ofG and y [member of] V(C).

1. Let x [member of] N (y) \ V (C) and c(x) = c(y). If we change the colour of y then no monochromatic [K.sub.1,3] appears.

2. Let x [member of] N (y) \ V (C) and c(x) [not equal to] c(y). If we change the colour of y then either

(i) there is exactly one monochromatic [K.sub.1,3], which has the centre at the vertex y and it forms Structure (1) or

(ii) there are exactly two monochromatic [K.sub.1,3]: one with the centre at the vertex y, the other with the centre at the vertex x and they form Structure (3) with a pre-root at x and a root at y.

Moreover, vertices of C do not form any alternating cycle and no new alternating cycle appears in any of these cases.

Now we present an algorithm which recolours vertices of an ([S.sub.2], [S.sub.2])-coloured cubic graph in such a way that the number of alternating cycles is decreased and the graph is still ([S.sub.2], [S.sub.2])-coloured. We input a cubic graph G which is ([S.sub.2], [S.sub.2])-coloured and a vertex v which is contained in an alternating cycle C. The algorithm returns an ([S.sub.2], [S.sub.2])-colouring in which the vertices of C do not form any alternating cycle and no new alternating cycle appears. An ordering X contains the vertices which are recoloured during the execution of the algorithm, initially X := [empty set]. Every vertex in X is recoloured only once.

Reduction Algorithm

Input: a cubic graph G with an ([S.sub.2], [S.sub.2]) -colouring, a vertex v which is contained in an alternating cycle. Output: a new ([S.sub.2], [S.sub.2])-colouring of G.

1. x := v.

2. Change the colour of x.

3. Append x to X.

4. If there is a structure which has the root at the vertex x then

4.1. if there is a structure in which the root is at the vertex x and the pre-root r is not in X then x := r and go to 2;

4.2. else find one vertex or two vertices such that after recolouring these vertices the structure is destroyed and no new structure appears.

To prove that the Reduction Algorithm is correct and decreases the number of alternating cycles we need the following properties of the ordering X:

Proposition 1 Let X = {[v.sub.1], [v.sub.2],..., [v.sub.t]}.

a) [v.sub.1] = v.

b) If [v.sub.i] was a root of Structure (1), then [v.sub.i+1] was a root of Structure (2).

c) If [v.sub.i] was a root of Structure (2), then [v.sub.i+1] was a root of Structure (4).

d) If [v.sub.i] was a root of Structure (3), then [v.sub.i+1] was a root of Structure (4).

e) If [v.sub.i] was a root of Structure (4), then [v.sub.i+1] was a root of Structure (1) or (3).

Proposition 2 Let X = ([v.sub.1], [v.sub.2],..., [v.sub.t]). Then [v.sub.i][v.sub.i+1] [member of] E(G) for i = 1, ..., t-1.

Proposition 3 No three successive vertices of the ordering X are coloured with the same colour.

Proposition 4 Let X = ([v.sub.1], [v.sub.2], ..., [v.sub.t]). If c([v.sub.i-1]) [not equal to] c([v.sub.i]) and c([v.sub.i+1]) [not equal to] c([v.sub.i]), then c([v.sub.i-2]) = c([v.sub.i-1]) = c([v.sub.i+1]) = c([v.sub.i+2]) for i = 3,... ,t - 2.

Proposition 5 Let X = ([v.sub.1], [v.sub.2], ..., [v.sub.t]).

a) If c([v.sub.i]) = c([v.sub.i-1]) and w [member of] N([v.sub.i]) \ X, then c(w) = c([v.sub.i]) for i = 2, ..., t.

b) If c([v.sub.i]) = c([v.sub.i+1]) and w [member of] N ([v.sub.i]) \ X, then c(w) [not equal to] c([v.sub.i]) for i = 1, ..., t-1.

c) If c([v.sub.i-1]) [not equal to] c([v.sub.i]) and c([v.sub.i+1]) [not equal to] c([v.sub.i]) and w [member of] N([v.sub.i]) \ X, then c(w) = c([v.sub.i]) for i = 2, ..., t-1.

[FIGURE 2 OMITTED]

Proposition 6 Let X = ([v.sub.1], [v.sub.2], ..., [v.sub.t]). Then one of the following conditions holds:

a) c([v.sub.1]) = c([v.sub.3]) = c([v.sub.4]), c([v.sub.2]) [not equal to] c([v.sub.1]) and the vertices in N([v.sub.1]) \ X are coloured with c([v.sub.1]) and the vertices in N([v.sub.2]) \ X are coloured with c([v.sub.2]);

b) c([v.sub.1]) = c([v.sub.4]), c([v.sub.2]) = c([v.sub.3]), c([v.sub.2]) = c([v.sub.1]) and the vertices in N([v.sub.1]) \ X are coloured with c([v.sub.1]) and the vertices in N([v.sub.2]) \ X are coloured with a colour other than c([v.sub.2]).

Lemma 2 Let G be a cubic graph whose vertices are ([S.sub.2], [S.sub.2])-coloured. Let C be an alternating cycle of G and v [member of] V(C). Then after execution of the Reduction Algorithm with the starting point in v we obtain an ([S.sub.2], [S.sub.2])-colouring of G in which the vertex v is not contained in any alternating cycle and this colouring does not contain any new alternating cycle.

Proof: By Observation 2 we have that if we change the colour of the vertex v, then either we obtain an ([S.sub.2], [S.sub.2])-colouring of G in which C is not alternating and no new alternating cycle appears or exactly one of Structures (1), (2) appears. From Observations 1 and 2 it follows that if we change the colour of a pre-root of any forbidden structure, then we destroy this structure and we obtain an ([S.sub.2], [S.sub.2])-colouring of G which does not contain any new alternating cycle, or we obtain a monochromatic [K.sub.1,3], or alternating cycles which are contained in Structure (4). Thus to complete the proof it is sufficient to show that in step 4.2 there exist appropriate vertices, i.e., the vertices such that after changing their colours the forbidden structure is destroyed and no new forbidden structure appears.

Let ([v.sub.1], [v.sub.2], [v.sub.t]) be vertices of the ordering X such that [v.sub.t] is a root of the forbidden structure which has the pre-root x belonging to X. Note that [v.sub.1] = v and every vertex of X was recoloured only once. Let S be the forbidden structure which appears after recolouring the vertex [v.sub.t]. Then [v.sub.t] is a root of S and x is a pre-root of S. By Proposition 2 we have that [v.sub.t] and x are adjacent. If x [not equal to] [v.sub.1] then two neighbours of x are in X. By Proposition 3, in X there are no three successive vertices with the same colour, so that S is isomorphic neither to Structure (2) nor to Structure (3). By Proposition 6, c([v.sub.1]) [not equal to] c([v.sub.2]), so if x = [v.sub.1], then also S is isomorphic neither to Structure (2) nor to (3). Thus we will consider two cases: when S is isomorphic to Structure (1) and when S is isomorphic to Structure (4). Since x [member of] X, assume that x = [v.sub.i]

[FIGURE 3 OMITTED]

Case 1 S is isomorphic to Structure (1).

First note that i [not equal to] 1, because by Proposition 6, the neighbours of [v.sub.1] which are not in X have the same colour as [v.sub.1]. Before [v.sub.t] was recoloured it had a colour different from c([v.sub.1]) and it was not in X, so the vertices [v.sub.1] and [v.sub.t] cannot be adjacent.

Assume that i [not equal to] t-1.

In Structure (1) the root is a centre of the monochromatic [K.sub.1,3] and the pre-root is a leaf of [K.sub.1,3], hence vertices [v.sub.t] and [v.sub.i] have the same colour. Thus before the vertex [v.sub.t] was recoloured, it had a colour other than [v.sub.i]. Therefore, before vertex [v.sub.t] was recoloured, the vertex [v.sub.i] had a neighbour outside the ordering X (the vertex [v.sub.t]) coloured with a colour other than c([v.sub.i]). Thus from the properties of the ordering X it follows that c([v.sub.i]) = c([v.sub.i+1]) (Proposition 5b) and c([v.sub.i-1]) = c([v.sub.i]) (Proposition 3).

In Structure (1) the pre-root is connected by an alternating path with the neighbour of the root, therefore there is an alternating path which starts at the vertex [v.sub.i] and goes through the vertex [v.sub.i-1]. Hence if we change the colour of [v.sub.i] no new forbidden structure appears and the algorithm stops (Fig. 3).

Suppose now that i = t-1. Since in Structure (1) there are two vertices [x.sub.1] and [x.sub.2] which can be a pre-root and the algorithm chooses as a pre-root the vertex [v.sub.t-1], it follows that both [x.sub.1] an [x.sub.2] are in X. Thus we can choose a vertex to recolouring similarly as in the case described above.

[FIGURE 4 OMITTED]

Case 2 S is isomorphic to Structure (4).

The pre-root of Structure (4) is contained in alternating cycles which also go through the vertex [v.sub.t]. By Proposition 1 the vertex [v.sub.t] was the pre-root of Structure (2) or (3) in which the root was [v.sub.t-1], hence there are no alternating cycles going through [v.sub.t-1]. Therefore i [not equal to] t-1.

We first consider the case i [not equal to] 1.

In Structure (4) the root and the pre-root are two successive vertices of an alternating cycle, therefore c([v.sub.t]) = c([v.sub.i]). Thus before we recoloured the vertex [v.sub.t], it had the same colour as [v.sub.i]. By Proposition 5 we have to distinguish two cases: one when c([v.sub.i]) [not equal to] c([v.sub.i+1]) and c([v.sub.i]) [not equal to] c([v.sub.i-1]) and the other when c([v.sub.i]) [not equal to] c([v.sub.i+1]) and c([v.sub.i]) = c([v.sub.i-1]).

Subcase 2.1 c([v.sub.i]) [not equal to] c([v.sub.i+1]) and c([v.sub.i]) [not equal to] c([v.sub.i-1]).

From Proposition 4 it follows that c([v.sub.i-2]) = c([v.sub.i-1]) = c([v.sub.i+2]). Every alternating cycle of the structure S contains the root [v.sub.t] and the pre-root [v.sub.i]. Therefore, all these cycles contain the vertex [v.sub.i-1] or [v.sub.i+1].

First suppose that both [v.sub.i-1] and [v.sub.i+1] have at most one neighbour coloured with their colour. Then at least one of the vertices [v.sub.i-1], [v.sub.i+1], say [v.sub.i-1], is contained in one of the alternating cycles of S. If we change the colour of [v.sub.i] and [v.sub.i-1], then we destroy the structure S and no new structure appears, so the algorithm stops (Fig.4 (a)).

Assume now that only one of the vertices [v.sub.i-1], [v.sub.i+1] has exactly one neighbour coloured with the same colour, say [v.sub.i-1] has exactly one neighbour coloured with c([v.sub.i-1]) and [v.sub.i+1] has two neighbours coloured with c([v.sub.i+1]). Note that every alternating cycle of the structure S contains the vertex [v.sub.i-1]. If we recolour the vertex [v.sub.i-1] then we destroy S and no new structure appears, so the algorithm stops (Fig.4 (b)).

[FIGURE 5 OMITTED]

Subcase 2.2 c([v.sub.i]) [not equal to] c([v.sub.i+1]) and c([v.sub.i]) = c([v.sub.i-1]).

Note that every alternating cycle of S contains the vertex [v.sub.i+1]. If we recolour the vertex [v.sub.i] then we destroy S and no new structure appears because now the vertex [v.sub.i-1] has a colour other than c([v.sub.i]). Thus the algorithm stops (Fig. 5).

Suppose now that i = 1. Since in Structure (4) there are two vertices [x.sub.1] and [x.sub.2] which can be a pre-root and the algorithm chooses as a pre-root the vertex [v.sub.1], it follows that both [x.sub.1] an [x.sub.2] are in X. Thus we can choose vertices to recolouring similarly as in the previous case. [there does not exist]

Lemma 3 For any cubic graph there is an acyclic ([S.sub.2], [S.sub.2])-colouring.

Proof: Let G be a cubic graph. By Lemma 1, there is an ([S.sub.2], [S.sub.2])-colouring of G. Suppose that there is no acyclic ([S.sub.2], [S.sub.2])-colouring of G. Let c be an ([S.sub.2], [S.sub.2])-colouring of G in which the number of alternating cycles is minimum. Let C be an alternating cycle and v [member of] V(C). By Lemma 2, after execution of the Reduction Algorithm with the starting point in v we obtain an ([S.sub.2], [S.sub.2])-colouring of G which has fewer alternating cycles than c, a contradiction. [there does not exist]

Proof of Theorem 2: Let G [member of] [S.sub.3]. If G is a cubic graph then, by Lemma 3, the Theorem holds. Otherwise there is a cubic graph F such that G [subset or equal to] F. Clearly, an acyclic ([S.sub.2], [S.sub.2])-colouring of F is also an acyclic ([S.sub.2], [S.sub.2] ) -colouring of G. [there does not exist]

3 The complexity of acyclic ([S.sub.2], [S.sub.2])-colourings of cubic graphs

In this section we present a polynomial algorithm which produces an acyclic ([S.sub.2], [S.sub.2]) -colouring of a cubic graph G of order n. In the algorithm we first find an ([S.sub.2], [S.sub.2])-colouring of G. Then we find an alternating cycle and using the Reduction Algorithm we recolour the vertices of G to destroy this alternating cycle in such a way that the graph G is still ([S.sub.2], [S.sub.2])-coloured. To find an alternating cycle we use the following function:

Function Cycle(v)

Input: a cubic graph G with a 2-colouring, a vertex v.

Output: an alternating cycle C containing v or a message that such a cycle does not exist.

1. G' := G[W], where W [subset or equal to] E(G) is the subset of bichromatic edges.

2. T := the BFS tree of the graph G' with the root in v.

3. Let [v.sub.1], [v.sub.2], [v.sub.3] be the neighbours of v.

4. V; := the set of descendants of [v.sub.l] in T, for l = 1, 2, 3.

5. If there is an edge xy [member of] E(G') such that x [member of] [V.sub.l], y [member of] [V.sub.l'] and l [not equal to] l' then

5.1. C:= the cycle of the graph T + xy;

5.2. output the cycle C.

6. else output the message that there are no alternating cycles containing v.

We can also use Function Cycle in step 4.1 of the Reduction Algorithm to determine whether the graph contains Structure (4). The algorithm works as follows:

Colour Acyclic Algorithm

Input: a cubic graph G of order n.

Output: an acyclic ([S.sub.2], [S.sub.2])-colouring of G.

I Find an ( [S.sub.2], [S.sub.2] ) -colouring of G.

II Mark each vertex of G as not visited.

III For each vertex v which is not visited do

A. use Function Cycle(v) to decide whether there is an alternating cycle C containing v;

B. if there is an alternating cycle C containing v then apply the Reduction Algorithm with the starting point in v to obtain an ([S.sub.2], [S.sub.2])-colouring of G such that the vertices of C do not form an alternating cycle and no new alternating cycle appears;

C. mark v as visited.

Theorem 3 There is a polynomial algorithm which produces an acyclic (S 2, S 2)-colouring of a cubic graph.

Proof: We discuss the running time of the Colour Acyclic Algorithm and we show that it is O([n.sup.3]), where n is the order of the input graph. Step I can be done due to Lemma 1. Moreover, it is easy to observe that a simple, iterative algorithm produces such a colouring in O(n) time. Clearly, Function Cycle(v) takes O(n) time. By Lemma 2, we have that after visiting each vertex v of G at most once and executing the Reduction Algorithm with the starting point in v, we obtain an acyclic ([S.sub.2], [S.sub.2])-colouring of G.

We now estimate the time complexity of the Reduction Algorithm. Finding a forbidden structure in step 4 takes O(n) time (we use Function Cycle to find Structure (4), Structures (1)-(3) can be found in O(1) time). The loop is iterated at most [intersection] times. From the proof of Lemma 2, it follows that step 2 can be implemented to run in O(1) time. Thus, on the whole, the Colour Acyclic Algorithm takes O([n.sup.3]) time. [there does not exist]

4 Acyclic ([S.sub.2], [S.sub.2])-colourings of graphs from [S.sub.4]

By Theorem 1 we have that there are graphs with maximum degree 4 which do not have any acyclic ([S.sub.2], [S.sub.2] )-colouring. We show that it is an NP-complete problem to decide if a graph with maximum degree 4 has an acyclic ([S.sub.2], [S.sub.2])-colouring, i.e., we prove the following:

Theorem 4 The recognition of graphs having an acyclic ([S.sub.2], [S.sub.2])-colouring for graphs with maximum degree 4 is NP-complete.

Before we present the proof, let us consider several graphs. First of all the graph B. It is easy to see that B has an acyclic ([S.sub.2], [S.sub.2])-colouring.

[FIGURE 6 OMITTED]

Lemma 4 For every acyclic ([S.sub.2], [S.sub.2])-colouring of the graph B, one colour class induces the graph [K.sub.3] and the second induces the graph [P.sup.3].

Proof: Suppose first that b, c, [member of] are coloured with the same colour. Then all the other vertices must be coloured with the other one. But then there is an alternating cycle induced by the vertices a, b, c, d, e, f. Suppose now, without loss of generality, that [member of] is coloured with colour 1 and b, c are coloured with colour 2. Then a must be coloured with colour 2 since otherwise the vertices a, b, c, [member of] would induce an alternating cycle. That implies that the vertices d and f are coloured with colour 1 (because the vertices b, c have now two neighbours coloured with colour 2). Obviously we obtained an acyclic ([S.sub.2], [S.sub.2])-colouring of the graph and the set of vertices coloured with colour 1 induces [P.sup.3] and the set of vertices coloured with colour 2 induces [K.sub.3]. [there does not exist]

Let us now take a quick look on the graph G([C.sub.j]), which includes the graph B as an induced subgraph.

[FIGURE 7 OMITTED]

Observation 3 The graph G([C.sub.j]) has an acyclic ([S.sub.2], [S.sub.2])-colouring and the maximum degree of G([C.sub.j]) is 4.

From Lemma 4 the next one follows.

Lemma 5 There does not exist an acyclic (S 2, S 2)-colouring of the graph G([C.sub.j]) such that [v.sub.j1], [v.sub.j2], [v.sub.j3] are in the same colour class.

Lemma 6 Any non-monochromatic 2-colouring of the vertices [v.sub.j1], [v.sub.j2], [v.sub.j3] can be extended to an acyclic ([S.sub.2], [S.sub.2])-colouring of the graph G([C.sub.j]).

Proof: The graph B is an induced subgraph of the graph G([C.sub.j]), the non-monochromatic 2-colouring of the vertices [v.sub.j1], [v.sub.j2], [v.sub.j3] must be consistent with Lemma 4. By symmetry of G([C.sub.j]) it is enough to consider only the case when [v.sub.j3] is coloured with colour 1 and [v.sub.j1], [v.sub.j2] are coloured with colour 2. Then the vertices a, b must be coloured with colour 1 and the vertices c, d must be coloured with colour 2 and we obtain the acyclic ([S.sub.2], [S.sub.2])-colouring of the graph G([C.sub.j]). [there does not exist]

From the above proof Lemma 7 follows.

Lemma 7 In any acyclic ([S.sub.2], [S.sub.2])-colouring of the graph G([C.sub.j]) for every vertex [v.sub.i]-j, where i = 1, 2, 3, the colour class which contains the vertex [v.sub.i]j contains also exactly two neighbours of [v.sub.ji].

Now let us consider the graph H.

Lemma 8 In every acyclic ([S.sub.2], [S.sub.2])-colouring of the graph H, either the vertices {a, b, c, j, k, n, o,p, r} or the vertices {a, b, c, j, l, n, o, r, s} belong to the same colour class.

[FIGURE 8 OMITTED]

Proof: First, let us consider an induced subgraph H' of the graph H where V(H') = {a, b, c, d, e, f, g, h}. The graph B is an induced subgraph of H, so the vertices a, b, c, e, f, g must be coloured in accordance with Lemma 4. Thus suppose that the vertices e, b, f (f, g, c) are coloured with colour 1 and the vertices a, c, g (a, b, e) are coloured with colour 2. That implies that the vertex d (h) must be coloured with colour 2. Now the vertex a has two neighbours coloured with colour 2, so the vertex h (d) must be coloured with colour 1. But now the vertices a, b, c, f, g, h (a, b, c, d, e, f) induce an alternating cycle. It is easy to see that if we colour the vertices a, b, c with colour 1, we must colour all the other vertices with colour 2. Furthermore this colouring defines the only acyclic ([S.sub.2], [S.sub.2])-colouring of the graph H'.

It is obvious that the colouring of the graph H determines the colouring of the graph H. One can see that because the vertex [member of] has two neighbours coloured with colour 2 then the vertex o must be coloured with colour 1. Furthermore from the fact that the vertex d is coloured with colour 2 and the vertex o is coloured with colour 1 from Lemma 4 it follows that the vertices j, [intersection] must be coloured with colour 1 and the vertices i, m must be coloured with colour 2. The remaining part of the graph can be coloured in both ways. Either we colour the vertices k,p, r with colour 1 and the vertices l, s with colour 2 or we colour the vertices r, l, s with colour 1 and the vertices k,p with colour 2. In this way we obtain the acyclic ([S.sub.2],[S.sub.2])-colouring of the graph H. [there does not exist]

On the basis of the graph H we create the graph F (see Fig. 9).

Lemma 9 The graph F has an acyclic ([S.sub.2], [S.sub.2])-colouring and maximum degree of F is 4.

Lemma 10 In all acyclic ([S.sub.2],[S.sub.2])-colourings of F the vertices x and x' are coloured differently from the vertex a.

The proof of the above lemma follows directly from Lemma 8.

Finally, let us consider the graph G([x.sub.j]) which we create as it is shown in Figure 10. From Lemma 10 the next one follows.

Lemma 11 In every acyclic ([S.sub.2],[S.sub.2])-colouring of the graph G([x.sub.i]) for i = 1, ..., n, k = 1, ..., m the vertices [x.sub.ik] belong to the same colour class.

[FIGURE 9 OMITTED]

[FIGURE 10 OMITTED]

To determine the complexity of the problem to decide if a given graph G [member of][S.sub.4]has an acyclic ([S.sub.2],[S.sub.2])-colouring we will use the 3NN-SAT problem. The NP-completeness of 3NN-SAT was proved in[6]

Proof of Theorem 4: Clearly our problem is in NP. In our proof we will make a polynomial-time reduction from the 3NN-SAT problem, which belongs to the class NP-c, to our problem. Let C = {[C.sub.1], ..., [C.sub.m]} be a set of clauses and let V = {[x.sub.1], [x.sub.1]} be a set of Boolean variables. Furthermore, [C.sub.j][subset or equal to]V and for j = 1,2, ..., m [C.sub.j] = ([c.sub.j1], [c.sub.j2], [c.sub.j3]). In 3NN-SAT we ask if there is a truth assignment such that in each clause there exist at least one true variable and at least one false variable. Note that there are no negative variables. Given an instance of 3NN-SAT we create an instance of our problem, i.e., the graph G in the following way. For each clause we create the graph G([C.sub.j]) and for each variable [x.sub.i] [member of] V we create the graph G([x.sub.i]). To obtain the whole graph G we have to connect the graphs G([C.sub.j]) and G([x.sub.i]). To do that for i = 1, ..., n, k =1, ..., m, p = 1, 2, 3 we add an edge [x.sub.ik][v.sub.kp], where [x.sub.ik][member of]V(G([x.sub.i])) and [v.sub.kp][member of]V(G([C.sub.j])), if and only if the variable [x.sub.i] is [c.sub.kp]. From Lemma 7 and the construction of the graph G a further Lemma follows.

Lemma 12 In every acyclic ([S.sub.2],[S.sub.2])-colouring of the graph G for j = 1, ..., m and p = 1,2,3 the vertex [v.sub.jp][member of]V(G([C.sub.j])) has exactly one neighbour [x.sub.i] in exactly one graph G([x.sub.i]) where 1 [less than or equal to] i [less than or equal to] n and moreover [x.sub.i] belongs to a different colour class than [v.sub.jp].

Let us suppose that the 3NN-SAT problem has a solution. We obtain an acyclic ([S.sub.2],[S.sub.2])-colouring of the graph G in the following way. For each true variable [x.sub.i] we colour every vertex [x.sub.ik][member of]V(G([x.sub.i])) with colour 1 and for each false variable [x.sub.i] we colour every vertex [x.sub.ik][member of]V(G([x.sub.i])) with colour 2 where i = 1,n, k = 1,m. We colour the neighbours of the vertices [x.sub.ik][member of]V(G([x.sub.i])) in the graph G([C.sub.j]) differently from [x.sub.ik]. From Lemmas 5, 6, 8, 11 and 12 we have that such 2-colouring can be extended to an acyclic ([S.sub.2],[S.sub.2])-colouring of the graph G.

Now suppose that the graph G has an acyclic ([S.sub.2],[S.sub.2])-colouring. To obtain a solution of the 3NN-SAT problem we assign true value to every variable [x.sub.i][member of] V for which the corresponding vertex [x.sub.ik][member of] V (G([x.sub.i])) is coloured with colour 1 where i = 1, ..., n, k = 1, ..., m. Furthermore we assign false value to every variable [x.sub.i][member of] V for which the corresponding vertex [x.sub.ik][member of] V(G([x.sub.i])) is coloured with colour 2 where i = 1, ..., n, k = 1, ..., m. The correctness of this assignment follows from Lemmas 5, 11 and 12. [there does not exist]

received July 18, 2008, revised January 5, 2010, accepted February 16, 2010.

References

[1] P. Boiron, E. Sopena, L. Vignal, Acyclic improper colourings of graphs with bounded degree, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 49 (1999) 1-9.

[2] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236.

[3] O.V. Borodin, A.V. Kostochka, D.R. Woodall, Acyclic colorings of planar graphs with large girth, J. London Math. Soc. 60 (1999) 344-352.

[4]M.I. Burstein, Every 4-valent graph has an acyclic 5-coloring, SoobsC Akad. Gruzin. SSR 93 (1979) 21-24 (in Russian).

[5] G. Fertin, A. Raspaud, Acyclic coloring of graphs of maximum degree five: Nine colors are enough, Information Processing Letters 105 (2008) 65-72.

[6] M. R. Garey, D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP Completeness, W. H. Freeman and Company, New York, 1979.

[7] B. Grunbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-412

[8] A.V. Kostochka, Upper bounds of chromatic functions of graphs, Ph.D. Thesis, Novosibirsk, 1978 (in Russian).

[9] S. Skulrattanakulchai, Acyclic colorings of subcubic graphs, Information Processing Letters 92

(2004) 161-167.

Mieczyslaw Borowiecki

Katarzyna Jesse-Jozefczyk

Anna Fiedorowicz

Elzbieta Sidorowicz

Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Gora, Poland

{m.borowiecki,a.fiedorowicz,k.jesse-jozefczyk,e.sidorowicz} @wmie.uz.zgora.pl

Printer friendly Cite/link Email Feedback | |

Author: | Borowiecki, Mieczyslaw; Jesse-Jozefczyk, Katarzyna; Fiedorowicz, Anna; Sidorowicz, Elzbieta |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Geographic Code: | 4EXPO |

Date: | Jan 1, 2010 |

Words: | 7380 |

Previous Article: | On economical set representations of graphs. |

Next Article: | An improved bound on the largest induced forests for triangle-free planar graphs. |

Topics: |