Contents ... Previous ... References
A Survey of Hereditary Properties of Graphs

6. Complexity Results

Let P and R= P1 . . . Pk be given (induced) hereditary properties. The (P : R)-partition (colouring) problem is stated as follows.

(P : R)-PARTITION ((P : R)-PART, for short).
INSTANCE: A graph G P.
QUESTION: Does there exists a (P1, . . . ,Pk)-partition of G?

The question can be of course reformulated in the following way: Is the graph G R-partitionable?

For some hereditary properties R, the problem (I : R)-PART is not even decidable. For some such examples see [23]. However, for many properties P and R the problem (P:R)-PART is well defined.

Let R = P1 . . . Pk. Note, that if (I:Pi)-PART is in NP for some i (it means it is NP-hard to decide whether a graph belongs to Pi), then (I:R)-PART NP. Let be a hereditary property defined by C() =min{:H C(R)}. Then the complexity of (I:R)-PART and (I:)-PART are the same, as the graph G is R-partitionable if and only if is -partitionable.

For the used complexity terminology see [43].

6.1 Ok-Partition

Theorem 69.([43])
(a) For k2 the problem (I:Ok)- PART is in P.
(b) For k3 the problem (I:Ok)- PART is NP-complete.

Brooks' Theorem implies that 3-colourability of a graph with maximum vertex degree 3 can be determined in polynomial time (we should only verify that the graph does not contain K4). Thus, the problem (S3 : O3)-PART is in P.

Since Brooks' Theorem applies to all graphs, then it might be expected that with the additional restriction of planarity a stronger result could be obtained. Unfortunately, it does not so.

Theorem 70.([91],[43]) The problem (T3 S4 : O3)-PART is NP-complete.

6.2 List Colouring

The LIST COLOURING problem includes graph k-colourability as a particular case by putting L(v)={1,. . . ,k} for all vV(G). Hence, the LIST COLOURING problem is NP-complete even if all lists have length three. Let us denote by LC[P:(k,s)] and LC[P:(=k,s)] the following two subproblems.

LC[P:(k,s)]
INSTANCE: A graph GP and a collection of lists {L(v): |L(v)|k, vV(G)}, and each colour occurs in at most s lists.
QUESTION: Does there exists a list colouring of G?

LC[P:(=k,s)]
INSTANCE: A graph GP and a collection of lists {L(v): |L(v)|=k, vV(G)}, and each colour occurs in at most s lists.
QUESTION: Does there exists a list colouring of G?

It was observed in [36] and [100] that LC[I:(2,)] is in P while LC[I:(3,)] is NP-complete.

Theorem 71.([63]) Let k3 be an arbitrary fixed integer. Then
(a) LC[I:(=k,k)] is in P,
(b) LC[I:(=k,k+1)] is NP-complete.

For k=3 the last problem remains NP-complete even for a class of planar graphs.

Theorem 72.([63]) LC[T3 S3:(3,3)] is NP-complete.

Theorem 73. The following cases of the LIST COLOURING problem are in P.
(a) [63]: LC[I:(2,)],
(b) [63]: LC[I:(,2)],
(c) [63]: LC[S2:(k,s)],
(d) [33]: LC[I:(deg(v),*)], where (deg(v),*) denotes a collection of lists with |L(v)|deg(v) for all vV(G) and |vV(G)L(v)|(G).

6.3 (I:Hom(H))-Part

The complexity of (I:Hom(H))-PART for undirected graphs was determined by Hell and Nesetril in [55].

Theorem 74.([55])
(a) If H is bipartite, then (I:Hom(H))-PART is in P.
(b) If H is not bipartite, then (I:Hom(H))-PART is NP-complete.

6.4 (P1, . . . , Pk)-Partition

Let P and R = P1 . . . Pk be given (induced) hereditary properties. It is easy to see that for some properties P and R the (P:R)-PART is polynomial. For example, if P = Okm then P R = (Om)k, k1, m2. By Ramsey's theorem there is a polynomial time algorithm for an (I:R)-PART, when R = Qk, F(Q) = {Km,l}. But we do not know it explicitly, as the determination of the precise value of the Ramsey numbers is a very difficult problem.

In [23] Brown stated the following conjecture.

Conjecture 75. Let R = Qk, F(Q) = {H: |V(H)| 3}. Then (I:R)-PART is NP-complete for any k2.

Conjecture 75 has been verified in [23] for:
(a) H=H1+ H2 (the join of two nonempty graphs) and k3,
(b) H is 2-connected and k2.

In particular, Conjecture 75 is true for:
(1) H=Km, m3, k2,
(2) H=Cm, m3, k2,
(3) H=Pm, m=3,4, k3 and for m5, k2.

One of the most intriguing problems is the following
Problem. Does Conjecture 75 is true for H=P3 and k=2?

The following theorem provides some particular result.

Theorem 76.([51]) Let R = Ok-r Dr1. Then (I : R)-PART is NP-complete for all k3 and 0rk.

For k=2, in [51] the following results are proved.

Theorem 77.([51])
(a) (S6 : O D1)-PART is NP-complete,
(b) (I : D21)-PART is NP-complete.

Theorem 78.([32]) (I : Skd )-PART is NP-complete for any k3 and d0.

Question :[32] What is the complexity of (Sk(d+1) : Skd)-PART?

6.5 (P1, . . . , Pk)-Partition of Planar Graphs

It is well-known [28] that every planar graph has vertex arboricity at most 3, so (T3 : D31)-PART is always true. Stein [90] (see also [49] and [10]) strengthened this result by proving that every planar graph can be partitioned into two forests and an edgeless subgraph, so (T3 : O D21)-PART is always true. On the other hand, Stein [90] proved that a maximal planar graph G has vertex arboricity 2 if and only if the dual G* (which is planar, cubic and 3-connected) is hamiltonian.

But in [42] it is proved that HAMILTONIAN CYCLE problem is NP-complete even when restricted to planar, cubic and 3-connected graphs. From this it follows that (T3 : D21)-PART is NP-complete.

Theorem 79. The following problems are NP-complete
(a) [44]: (T3 S4 : O3-PART,
(b) [51]: (T3 S4 : O D1)-PART,
(c) [32]: (T3 S4 : S21)-PART,
(d) [51]: (T3 : O2 D1)-PART for graphs in which each face has size 3 or 4,
(e) [32]: (T3 : S2d)-PART for d1,
(f) [32]: (T3 : S31)-PART.

Conjecture 80 ([51]) (T3 : O2 D1)-PART is NP-complete for maximal planar graphs.

1997