# Deciding k-colourability of ￠ -free graphs in polynomial time

Deciding k-colourability of

November 1, 2006

Abstract The problem of computing the chromatic number of a -free graph is known to be NP-hard. In contrast to this negative result, we show that determining whether or not a -free graph admits a -colouring, for each ?xed number of colours , can be done in polynomial time. If such a colouring exists, our algorithm produces it.

1 Introduction
A -colouring of a graph is an assignment of colours to the vertices of so that no two adjacent vertices receive the same colour. The -COLOURABILITY is the problem of determining whether or not a given graph admits a -colouring. The optimization version of the problem asks to ?nd a -colouring of with minimum , . called the chromatic number of and denoted The -COLOURABILITY is one of the central problems of algorithmic graph theory with numerous applications [4]. It is also one of the most dif?cult problems: it is NP-complete in general [12] and its optimization version is even hard to approximate [13]. Moreover, the problem remains dif?cult in many restricted graph families, for example triangle-free graphs [17] or line graphs [11] (in which case it coincides with the EDGE -COLOURABILITY). On the other hand, when restricted to some other classes, such as graphs of vertex degree at most [2] or perfect graphs [8], the problem can be solved in polynomial time. Ef?cient polynomial-time algorithms for ?nding optimal colourings are available for many particular subclasses of perfect graphs, including chordal graphs [6], weakly chordal graphs [9], and comparability graphs [5]. All the aforementioned examples refer to graph classes possessing the property that with any graph they contain all induced subgraphs of . Such classes are known in the literature under the name of hereditary classes. Any
Physics and Computer Science, Wilfrid Laurier University, Canada. Research supported by NSERC. choang@wlu.ca RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854, USA. mkaminski@rutcor.rutgers.edu RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854, USA. lozin@rutcor.rutgers.edu Computing and Information Science, University of Guelph, Canada. Research supported by NSERC. sawada@cis.uoguelph.ca Computing and Information Science, University of Guelph, Canada. email: xshu@uoguelph.ca

email: email: email: email:

1









 

Keywords: graph colouring, dominating clique, polynomial-time algorithm,

-free graph

§



?





?

? ¨

? ¨

¤

! 









?

Ch?nh T. Ho` ng ? a

Marcin Kami? ski n

? ??

-free graphs in polynomial time











%

#

\$

"



&



3

4

5 ?? ?? ?? ?? ...

6 ? ? ? ? ...

...

...

...

...

...

...

hereditary class can be described by a unique set of minimal graphs that do not belong to the class, so-called forbidden induced subgraphs. A nice survey on colouring vertices of graphs in hereditary classes can be found in [18]. An important line of research of this type deals with -free graphs, i.e., classes excluding a path on vertices as an induced subgraph. Sgall and Woeginger showed in [21] that - COLOURABILITY is NP-complete for -free graphs and - COLOURA -free graphs. The last result was improved in [16], where the authors claim that BILITY is NP-complete for by modifying the reduction from [21] - COLOURABILITY can be shown to be NP-complete for -free graphs. On the other hand, the -COLOURABILITY problem can be solved in polynomial time for -free graphs as they , the complexity of the problem is generally unknown, constitute a subclass of perfect graphs. For except for the case of -colourability of -free [20, 21] and -free graphs [19]. Known results on the COLOURABILITY problem in classes of -free graphs are summarized in Table 1 (under columns 5 and 6, is matrix multiplication exponent known to satisfy [3]). In this paper, we focus on the minimal class from Table 1 where the -COLOURABILITY problem is unsolved, i.e., the class of -free graphs. This class is “stubborn” with respect to various graph problems. For instance, -free graphs constitute a unique minimal class de?ned by a single forbidden induced subgraph with unknown complexity of the MAXIMUM INDEPENDENT SET and MINIMUM INDEPENDENT DOMINATING SET problems. -free graphs, which includes, among Many algorithmic problems are known to be NP-hard in the class of others, DOMINATING SET [14] and CHROMATIC NUMBER [15]. In contrast to the NP-hardness of ?nding the chromatic number of a -free graph, we show that - COLOURABILITY can be solved in this class in polynomial time for each particular value of . In the case of a positive answer, our algorithm yields a valid -colouring. Along with the mentioned result on 3- COLOURABILITY of -free graphs, our solution generalizes several other previously studied special cases of the problem, such as - COLOURABILITY of -free graphs [16] and - COLOURABILITY of -free graphs containing a dominating clique on four vertices [10]. We also note the algorithm in [7] that colours a -free graph with colours. The remainder of the paper is organized as follows. In Section 2 we give relevant de?nitions, concepts, and notations. In Section 3, we present our recursive polynomial time algorithm that answers the -colourability question for -free graphs. The dif?cult step in the algorithm is detailed using two different approaches. We conclude with a summary of our results in Section 4 along with a list of open problems.

2 Background and De?nitions
In this section we provide the necessary background and de?nitions used in the rest of the paper. For starters, we assume that is a simple undirected graph where and . If is a subset of , then 2

)



q

?



Q

U 



V W

?Pf?P?  ?a

?

3 X? ?(? ??

I P

E F

Table 1: Known complexities for -colourability of

-free graphs

BDA@  BDA@  BDA@  B DA@
...

BDA@  BDA@  BDA@  B DA@

BC5@  BC5@  BC5@  B C5@

 P

B B C5@ CA@ B B C5@ CA@ B B C5@ CA@ B CA@  7 X? ?(???? h i E G  S ?P  Q

ce wr s q s ?yxgbvutYr



ea ca H X fbdb`Y)

54361  54361  54361  54361  (94361 (4721 54361 87  8      E p H Q ?? ?F?  a  TSP R  C  g 

???F??? a  X

54321  54321  54321  54321  54321  

3 4 5 6 7 ...

7 ? ? ? ? ? ...

8 ? ?

9 ?

10 ?

11 ?

12 ?

... ... ... ... ... ... ...

 p

)' 0( E D  C Q

D EFINITION 2 Given a graph , an integer and for each vertex , a list of colours, the -list colouring problem asks whether or not there is a colouring of the vertices of such that each vertex receives a colour from its list.

Our general approach is to take an instance of a speci?c colouring problem for a given graph and replace it with a polynomial number of instances such that the answer to is “yes” if and only if there is some instance that also answers “yes”. This For example, consider a graph with a dominating vertex where each vertex has colour list listing corresponds to our initial instance . Now, by considering different ways to colour , the following four instances will be equivalent to :

: : :

and the remaining vertices have colour lists and the remaining vertices have colour lists

and the remaining vertices have colour lists

In general, if we recursively apply such an approach we would end up with an equivalent set with an exponential number of colouring instances.

3 The Algorithm
Let be a connected -free graph. This section describes a polynomial time algorithm that decides whether or not is -colourable. Our strategy is as follows. First, we ?nd a dominating set of which is a clique with at most vertices or a . There are only a ?nite number of ways to colour the vertices of with colours. For each of these colourings of , we recursively check if it can be extended to a colouring of . Each of these subproblems can be expressed by a restricted list colouring problem. We now describe the algorithm in detail. 3





|



|

pxdakhQabdabd?nl H g ram pxdkhQbd?nl Ha a ram pxdkhQbd?nl Ha a gam pHa a ga r xdkhQbdb0l

|

e i

 i

p a l X xHdkQ??9w g X z9w r X z9w m X y9w

:

and the remaining vertices have colour lists

, , ,

.

k4fjg

D EFINITION 3 The restricted -list colouring problem is the -list colouring problem in which the lists colours are subsets of .

pHa a ga ram xdkhQbdbd?nl



e W

w

 i4fhg

r

r

f





w

wwwae saS saR ooo?qf?qftps



r

p awwwa ram qd0ooobd?nl 

 p

T HEOREM 1 Every connected

-free graph has either a dominating clique or a dominating

 F

-free graphs is from Bacs? and Tuza [1]: o .

d

d

?

D EFINITION 1 A set of vertices one vertex in .

is said to dominate another set

?



we let denote the subgraph of joining any two vertices in it.

induced by

. A stable set is a set of vertices such that there is no edge



r

u vs

?

???Y 

, if every vertex in

of

   

V {s e qs S qs R s

The algorithm is outlined in 3 steps. Step 2 requires some extra structural analysis and is presented using two different approaches in the following subsections. Algorithm 1. First, we check if contains a dominating set of size at most . If no such a set is found, then is not -colourable. Otherwise, let be a dominating set in , which is either a clique with at most vertices or a . Let the vertices of the dominating set be with . Since is a dominating set, we can partition the remaining vertices into ?xed sets , , such that vertices in are adjacent to , and for , vertices in are adjacent to but not to . The colour list of the vertices in the ?xed sets have size at most since each vertex in is already assigned a colour. This gives rise to our original restricted list-colouring instance . 2. Two vertices are dependent if there is an edge between them and the intersection of their colour lists is non-empty. In this step, we remove all dependencies between each pair of ?xed sets. This process will create a set , equivalent to , of a polynomial number of colouring instances. Two different methods for performing this step are outlined in the following subsections. 3. For each instance from Step 2 the dependencies between each pair of ?xed sets has been removed which means that the vertices within each ?xed set can be coloured independently. Thus, for each instance we recursively see if each ?xed set can be coloured with the corresponding restricted colour lists (the base case is when the colour lists are a single colour). If one such instance provides a valid -colouring then return the colouring. Otherwise, the graph is not -colourable. As mentioned, the dif?cult part is reducing the dependencies between each pair of ?xed sets (Step 2). We present two different approaches to handle Step 2. The ?rst is conceptually simpler while the second includes additional structural results.

3.1 Removing the Dependencies Between Two Fixed Sets: Method I
be the set of colours that appear in the lists of vertices of a set . Let and be two ?xed sets. Let Note that and . We remove dependencies between and by applying the following procedure. Procedure One

Now, we describe how to remove dependencies between two stable sets and . Let (respec(respectively, ) that are dependent on some vertices of (respectively, tively, ) be the set of vertices of ). Note that is non-empty if and only if is non-empty.

4

? Y?

? ??

? ?X ? ?p5?

L EMMA 1 If

, there exists a vertex in

that is adjacent to all vertices in

.

? ?d

? 5?

? !?

2. For each

and each

, remove dependencies between

and

awwwaS aR ?ooo???do?d

?

d X ? y??

 R u ?awwwaS aR ?? ?(?ooo?????Y?

? X ? ???

m???d0ooobd???? awwwa ram X m ? awwwa ram X ??d?ooobd?yp? R u  ??Y? m ? d ? ?? ?d d ? ?!? m?

1. Find a ). If

-colouring of (respectively, ) with stable sets or cannot be -coloured, then cannot be -coloured.

(respectively,

.

?s

R W?







d

r | m ? ?2 po?4??y?~a0owooa?(?l R w w R~ ? x~ ? C? ) y?A? ????a?ooo?D????? wwwaS aR |  ???) n?~?ooo?x?~t~ E awwwaS aR  g } v9 d ? ? ?  ? r

m ?  ?? g? t6?voY?dh?t ??

? ??

?

|

m ? ??

?pooo?{f?qf???l wwwae saS saR s

m ?  ?? g? v6zo???h?? ??

? qs



R (~

? A?

e C

??h??? g?

??



?

Proof. Let be a vertex of with a maximal neighborhood in . Assume there exists a vertex that is (different than ) adjacent to . Also, by the choice not adjacent to . Then, there must exist a vertex of , there must exist a vertex that is adjacent to but not . Since and belong to different ?xed sets, there exists a vertex in the dominating set such that either is adjacent to but not , or is adjacent to but not . But then is an induced ; a contradiction. This lemma states that as long as and are non-empty, we can ?nd a vertex that dominates . Now given such a vertex , we can create new equivalent colouring instances by assigning to (i) a colour from and (ii) the list . In the former instances the vertices in lose the colour assigned to from their lists i.e., decreases by one. In the latter instance, the vertex is no longer dependent on any vertex in and is thus removed from . In this case, we recursively repeat this process until is empty by ?nding a new vertex in that dominates . This will result in at most new colouring instances where either is empty or has decreased by one from its initial state. To reduce to zero, we repeatedly apply this process at most times. Thus, we can completely remove the dependencies between and by producing at most new equivalent colouring instances. Analysis. To remove the dependencies between each and requires new equivalent instances. Thus, to remove the dependencies between each pair of ?xed sets (Step 2 of Procedure One) requires new equivalent instances. Since there are ?xed sets, there are less than pairs of ?xed sets. Thus, to remove dependencies between each pair of ?xed sets (given the stable sets for each ?xed set) requires equivalent colouring on the graph with instances. To ?nd the stable sets for each ?xed set requires a single recursive the initial dominating set combined with the edges between the ?xed sets removed. Now, let denote the number of subproblems produced by the Algorithm where is the number of colours : used on a graph with vertices. From the previous analysis we arrive at the following recurrence where

A proof by induction shows

3.2 Removing the Dependencies Between Two Fixed Sets: Method II
For our second method for removing the dependencies between a pair of ?xed sets, it will be convenient to to the colours in its lists. For this purpose, let denote a ?xed set of vertices with associate a ?xed set colour list given by . We partition each such ?xed set into dynamic sets that each represents a unique subset of the colours in . For example: . Initially, and the remaining sets in the partition are empty. However, as we start removing dependencies, these sets will and one of its neighbors gets coloured 2, then dynamically change. For example, if a vertex is initially in will be removed from and added to . Recall that our goal is to remove the dependencies between two ?xed sets and . To do this, we remove the dependencies between each pair ( ) where is a dynamic subset of and is a dynamic subset of . By visiting these pairs in order from largest to smallest with respect to and then , we ensure that we only need to consider each pair once. Applying this approach, the crux of the reduction process is to remove the dependencies between a pair by creating at most a polynomial number of equivalent colourings. Now, observe that there exists a vertex from the dominating set found in Step 1 of the algorithm that dominates every vertex in one set, but is not adjacent to any vertex in the other. This is because and are subsets of different ?xed sets. without loss of generality assume that dominates . Now, consider the (connected) 5

heTSG??heTSC? R X R

 m ?? ± 7 ou Db?  S ° 7 tu Db? 7 ?d ?? u Db? Db? 7  u ? g? o ? ??h?!??? ? g? o ? ??h????? 7 b ? ?? ? ?? ??? ? ?? ¤ ? g? o ? ??h????? ? Y? ????h??9k?4¤jg ? g? ? ? ¤ ¤ ??? ????¤ ? ? ? ?? ?? ? ? p ?p?y?hoih??qh¤??h¤q?¨lY S aR aS aR a f  S aR qh¤??¤ f yh?oi? S aR S R qh¤a?W¤ f f ? ? S v¤ RD¤ ?? ?R ?§?{? ? 9??¤ ? ?S ? 5?
, implying our algorithm runs in polynomial time.

m X  ?F?jm??

? ??

?? ?S ?§?b? ?

? ? o??hg?t ?? ? g? o??j?t ?? ? ? ?  ? ?? ?? ? TeG R heTS? R w e  ? ? S ? R ? R ? R X R C???SC?vRG?DheC??TeFYDTSFYDheTSF??heTSF? ?W TE??? C? ·

S n? 



?

R D¤

? 7  1 X  tu Db?h2?i(??? w m ?  ? ? m ?  7  X  f??Y??????????  Db??F(???

? Y?

f

f

?a f?

?f?? ?a

heTSP R

) ?¨?4?g

)?????g ??

7

? ??

R D¤

S aR yh?ok? ? ?

¤ ????h?!?x4¤hg ? g? ? ?

(??? 

R D¤

??

R ?¤

? ? w

P

Q
Z Z
v

Graph H

and . If a component in is not adjacent to any vertex in then the vertices components of in have no dependencies with . The same applies for such components in . Since these components have with these components removed. no dependencies, we focus on the induced subgraph This graph is illustrated in Figure 1 where the small rectangles represent the components in and respectively. It is easy to observe that is connected (if not, then there are components of , each of which contains a vertex in and a vertex in ; it follows there are edges of and of such that induce a ). T HEOREM 2 Let be a connected -free graph partitioned into three sets , and where is adjacent to every vertex in but not adjacent to any vertex in . Then there exists at most one component in that contains two vertices and such that is adjacent to some component but not adjacent to another component while is adjacent to but not .

,

, ,

.

denote an arbitrary vertex from the component . Since is -free, there must be edges and , otherwise and would be s. An illustration of these vertices and components is given in Figure 2 - the solid lines. Now, if , then there exists a . Thus, and must be unique components, and must be different as well for the same reason. Similarly . Now since cannot be a , either is adjacent to or must be adjacent to . Without loss of generality, suppose the latter. Now implies that either or is adjacent to . If the latter, then would be a which implies that must 6

? a a?a V h?{hfa S h?0dq?  C V aR q??tp?

od{?? ?a

 C ???yh?qhf?nh??? ae a aS a

 p

e v?

??a{?~a?y?h0dq? V a?a V ?? S? V ? ?X S qzYD? S v? ?~????yh?0d{??i a aS a?a ? X 

?



? ?

Let

??Y?? S h?a R ?  

P ROOF : The proof is by contradiction. Suppose that there are two unique components and and components and from such that:

??6 

??6 

S6? b?~??? a ? 6??o?? S aR ??6 

f

?

pf (?l

R ?? od{?? ?a

??Y5?G?   ?R ? 

?

?p{?l??????y?Y??? f X ??6 ?  ??Y  V ? ?X e {zYv? R ?? 

?

Figure 1: Illustration of the graph

from two dynamic sets

e ?? V v? R C? S ?? S ? ?X R v?!D?

S ??

?~a V h?{hfa e h?0? a a

?

?

?



?

??Y  ? ? 

? a a da S h?qhfa R h?{?

V v? e ? S ? RD? S ? ? a 29??~0?

? ? ? e?

??Y5??  ?S ? ? ?

 C

??Y 

e? XS vz?v?

??(?~qhf?dq? a a a?a b?~??? a ? ?? ~ ? ? ? ? ? ? ? R ? ? ?a ?9?dq? ?

?

with

a b c d

Y1 Y2
v

Y3 Y4

Figure 2: Illustration for proof of Theorem 2

From Theorem 2, there is at most one component in that contains two vertices and such that is adjacent to some component but not adjacent to another component while is adjacent to but not . If such a component exists, then we can remove the vertices in from by applying the following general method for removing a component from a dynamic set . Procedure RemoveComponent

Since is -free, it has a dominating clique or (Theorem 1). If this dominating set can be coloured with the list , we consider all such colourings (otherwise we report there is no valid colouring for the given instance). For each case the colouring will remove all vertices in the component from to other dynamic sets represented by smaller subsets of available colours. Observe that since is ?xed, the number of such colourings is constant.

be adjacent to a maximal number of components in . If it is not adjacent to all P ROOF : Let components, then there must exist another vertex and components such that is adjacent to but not and is adjacent to but not . This implies that there is a where and unless and are adjacent. However by Theorem 2, they cannot belong to the same component in since such a component would already have been removed - a contradiction. Now, suppose that there are two components and in that does not dominate. Then there exists edges and such that is adjacent to and , but not nor . This however, implies the - a contradiction.

7

¤

¤

??j?t?W??h?t? g?? ? g?

Now we identify such an with each colour from

outlined in this claim and create equivalent new colouring instances by assigning and then with the list . If is assigned a colour from

R? ?R 5?k?

?

¤

¤

?{h¤a?y?h{fhoRih?aDz?F S a a ¤ X ? ? S aR u?v???D? ???? 

?S b?

Rb? ?

???? 

that is adjacent to all components in C LAIM 1 There exists a vertex components of except at most one.

. Moreover,

dominates all

?

S y?

¤

R (?

???? v?  S

 ?? ? ¤

¤

R p?

R D?

?

If there are still dependencies between and dynamically changes as and change):

, then we make the following claim (observing that the graph

?

?

|

?

?

|

 ? ??6u??   ? S ? 

|

??a S h?qhfa V h?{zX   a a? ??6  e F ? ?

??Yu!C?   ?R   ? ??¤ S ? ?

??h?t5C??j?t? g?? ? g? ¤ ?S a ? ? xh?a S h?Dh¤a R h?a Rx?X   S ? ? ?S a S v?6 bh??y4? ?t? Rbh?oi4? R ? ? ? aR

? v¤

9?|j?t? g?



????  ¤ ? S §? S ? ? S q¤ v? R ??  ? ??¤ ???? 

 p ?

V? R?

anyway. Thus, we end up with a

which is a contradiction to the graph being

S?

 C

, then all but at most one component will be removed from . If one component remains, by applying Procedure RemoveComponent. In the latter case, where is then we can remove it from assigned the colour list , will be removed from . If there are still dependencies between and , we repeat this step by ?nding another vertex . In the worst case we have to repeat this step at most times. Therefore, the process for removing the dependencies between two dynamic sets creates at most new equivalent colouring instances. Analysis. We have just shown that we require at most new equivalent colouring instances to remove the dependencies between two dynamic sets. Since each ?xed set contains at most dynamic sets, there are pairs of dynamic sets to consider between each pair of ?xed sets. Thus, removing the dependencies between two ?xed sets produces subproblems. Since there at most pairs of ?xed sets, this means that to remove the dependencies between all ?xed sets creates subproblems. As with the previous method, let denote the number of subproblems produced by the Algorithm where is the number of colours used on a graph with vertices. From the previous analysis we arrive at the following recurrence where : A proof by induction proves that , implying our algorithm runs in polynomial time. -free graphs, for a ?xed integer , can be solved in

4 Summary
This algorithm presented in this paper brings us one step closer to completely answering the question of when there exists a polynomial time algorithm for the - COLOURABILITY problem for -free graphs, given ?xed and . In particular, we now know that there exists a polynomial time algorithm when for any ?xed value of . Continuing with this vein of research, the following open problems are perhaps the next interesting avenues for future research:

Does there exist a polynomial time algorithm determine whether or not a

Two other related open problem mentioned are to determine the complexities of the SET and MINIMUM INDEPENDENT DOMINATING SET problems on -free graphs.

8

 i

?

Is the problem of -colouring a

-free graph NP-complete.

h ? 

Does there exist a polynomial time algorithm determine whether or not a

-free graph can 3-coloured. -free graph can 4-coloured.

MAXIMUM INDEPENDENT



H X ?)

E W





 i

C OROLLARY 1 Determining whether or not a , can be decided in polynomial time.

-free graph can be coloured with -colours, for a ?xed integer



 G

T HEOREM 3 The restricted -list colouring problem for polynomial time.

D4721  ? ? ?  

¤

S R  ?? u ?r21

???? 

??bd??¨???S d? u 4761 ×? ? 

??×bdx??tV ? tu 472?F(??? ? °  1 X  wf?mv?Y??? ??x?dx??¨? S ? tu ?????(???  × ? 7 7 (??? 



D4721 

¤

??bd??¨???S 4721 ×? 

¤ ??hg?????G??h?t? ? g? ?  

m X  yF?jm??

??j?t?C??j?t? g?? ? g? ¨??? u ?S ?r61 R ?  ) ? ? ?  ? 

References

[2] R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37, (1941), 194-197. [3] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, Vol. 9 No. 3(1990) 251-280. [4] D. de Werra and D. Kobler, Graph colouring: foundations and applications, RAIRO Oper. Res. 37 (2003) 29-66. [5] S. Even, A. Pnueli and A. Lempel, Permutation graphs and transitive graphs, J. Assoc. Comput. Mach. 19 (1972) 400-410. [6] F. Gavril, Algorithms for minimum colouring, maximum clique, minimum colouring by cliques, and maximum independent set of a chordal graph, SIAM J. Comput. 1 (1972) 180-187.

[8] M. Gr¨ tschel, L. Lov? sz and A. Schrijver, Polynomial algorithms for perfect graphs, Ann. Discrete Math. o a 21 (1984) 325-356. [9] R. Hayward, C. T. Ho` ng and F. Maffray, Optimizing weakly triangulated graphs, Graphs and Combinaa torics 5 (1989) 339-349. triangulated graphs, Graphs and Combinatorics 5 (1989) 339-349.

[11] I. Holyer, The NP-completeness of edge-colouring, SIAM J. Computing, 10 (1981) 718-720. [12] R. M. Karp, Reducibility among combinatorial problems. In: R. E. Miller and J. W. Thatcher (eds), Complexity of Computer Computations, Plenum Press, New York, (1972) 85-103. [13] S. Khanna, N. Linial and S. Safra, On the hardness of approximating the chromatic number, Combinatorica 20 (2000) 393-415. [14] D.V. Korobitsyn, On the complexity of determining the domination number in monogenic classes of graphs, Diskret. Mat. 2, N 3 (1990), 90-96 in Russian, translation in Discrete Mathematics and Applications, 2 (1992), no. 2, 191-199). [15] D. Kral, J. Kratochvil, Z. Tuza and G. J. Woeginger, Complexity of colouring graphs without forbidden induced subgraphs, in: WG 2001, LNCS 2204, (2001) 254-262. [16] V. Bang Le, B. Randerath, I. Schiermeyer, Two remarks on colouring graphs without long induced paths, in Report No. 7/2006 (Algorithmic Graph Theory), Mathematisches Forschungsinstitut Oberwolfach. [17] F. Maffray and M. Preissmann, On the NP-completeness of the -colourability problem for triangle-free graphs, Discrete Math. 162 (1996) 313-317. [18] B. Randerath, I. Schiermeyer, Vertex colouring and forbidden subgraphs – a survey, Graphs and Combinatorics, 20(1) (2004) 1-40.

9



 W

[10] C. T. Ho` ng, J. Sawada and Z. Wang, Colorability of a

-free graphs, manuscript, 2005.

 a  ?

[7] V. Giakoumakis and I. Rusu, Weighted parameters in (1997) 255-261.



[1] G. Bacs? and Z. Tuza, Dominating cliques in o 303-308.

-free graphs, Period. Math. Hungar. Vol. 21 No. 4 (1990)

-free graphs, Discrete Applied Math. 80

[20] B. Randerath, I. Schiermeyer, M. Tewes, Three-colourability and forbidden subgraphs. II: polynomial algorithms, Discrete Mathematics 251 (2002) 137-153. [21] J. Sgall, G. J. Woeginger, The complexity of colouring graphs without long induced paths, Acta Cybernetica 15(1), (2001) 107-117.

10

h

? ??

[19] B. Randerath, I. Schiermeyer, -colourability (2004) 299-313.

for

-free graphs, Discrete Applied Mathematics 136

g