On 3 3 -colorability of ( c ​ l ​ a ​ w , d ​ i ​ a ​ m ​ o ​ n ​ d ) (claw,diamond) -free graphs Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok, Ingo Schiermeyer Abstract The 3 3 -colorability problem is a well-known NP-complete problem and it remains NP-complete for ( c ​ l ​ a ​ w , d ​ i ​ a ​ m ​ o ​ n ​ d , K 4 ) (claw,diamond,K_{4}) -free graphs. Recently, 3 3 -colorability has been also considered for ( c ​ l ​ a ​ w , N 1 , 1 , 1 ) (claw,N_{1,1,1}) -free graphs. Here, a generalised net N i , j , k N_{i,j,k} is the graph obtained by identifying each vertex of a triangle with an endvertex of one of three vetex-disjont paths of lengths i , j , k i,j,k . We study the class of ( c ​ l ​ a ​ w , d ​ i ​ a ​ m ​ o ​ n ​ d , N i , j , k ) (claw,diamond,N_{i,j,k}) -free graphs for ( i , j , k ) ∈ { ( 1 , 1 , 3 ) , (i,j,k)\in\{(1,1,3), ( 1 , 2 , 2 ) , (1,2,2), ( 2 , 2 , 2 ) } (2,2,2)\} . We show that these graphs are 3 3 -colorable or contain a K 4 K_{4} or belong to some well-defined class of non 3 3 -colorable graphs. Moreover, we prove that there are only finitely many non 3 3 -colorable N 1 , 2 , k N_{1,2,k} -free graphs for any k ≥ 2 k\geq 2 , but there exist infinitely many non 3 3 -colorable N i , j , k N_{i,j,k} -free graphs for any 2 ≤ i ≤ j ≤ k . 2\leq i\leq j\leq k. Keywords: 4 -colorable graphs, forbidden induced subgraphs, perfect graphs, complexity Math. Subj. Class.: 05C15, 05C17, 68Q25, 68W40. 1 Motivation and Introduction We consider finite, simple, and undirected graphs. For terminology and notations not defined here, we refer to [ 1 ] . In this paper we will use the following notation. A diamond is a graph K_{4} with one edge deleted; a bull is a triangle with two pendant edges attached to two of the vertices of the triangle; and a net is a triangle with additional pendant edge at each vertex. A generalised net N_{i,j,k} has its pendant edges subdivided i-1,j-1,k-1 times respectively (see Fig. 1 .) (a) (b) (c) Figure 1 : The graphs called the bull, the net and N_{1,2,3} respectively. It is well-known that the k -colorability problem remains NP-complete in classes of graphs defined by one forbidden induced subgraph F , unless this subgraph is a linear forest. If F is not a linear forest then k -Colorability remains NP -complete. The cases when F is a triangle or a claw have been studied very intensively. The 3 -colorability problem was also stated for classes defined by pairs of forbidden induced subgraphs. In 2004, Randerath obtained structural results, listing all possible pairs of forbidden induced subgraphs, which can be saturated pairs implying 3 -colorability of a graph ( [ 11 ] ). There are also many algorithmic results, providing polynomial algorithms deciding whether or not a graph with a forbidden pair is k -colorable. For instance, for pairs (claw,P_{6}) , (claw,K_{1}+2K_{2}) ( [ 10 ] ), and quite recently for pairs (bull,S_{1,1,2}) and (bull,S_{1,2,2}) ( [ 4 ] , [ 5 ] ). Here, S_{i,j,k} is a tree consisting three paths of length {i,j,k} joining by identify one end-vertex of every path. In particular a claw is a graph S_{1,1,1} . Moreover, given a family \cal{H} of graphs and a graph G , we say that G is \cal{H} -free if G contains no graph from \cal{H} as an induced subgraph. In this context, the graphs of \cal{H} are referred to as forbidden induced subgraphs . Interestingly, the thorough structural analysis given by [ 5 ] provides that the only (bull,S_{1,1,2}) -free (and also (bull,S_{1,2,2}) -free) non- 3 -colorable graphs are build of diamonds, while in this paper we will see that the main families of (claw,diamond) -free graphs contain bull . For more results concerning complexity of coloring problems in classes defined by forbidden induced subgraphs, see [ 6 ] and surveys [ 3 ] , [ 9 ] . Our research has been motivated by a recent result about 3 -colorability of (claw,net) -free graphs [ 2 ] . First observe a necessary and useful fact for 3 -colorable graphs: Let G be a 3 -colorable graph containing an induced diamond. Then in any 3 -coloring of G the two nonadjacent vertices in an induced diamond receive the same color. Based on this observation in [ 2 ] the class of so called spindle graphs (cf. also [ 5 ] ) has been introduced, which all contain induced diamonds and which are all non 3 -colorable. Theorem 1 . [ 2 ] Let G be a connected, (claw,net) -free graph. Then 1. G contains K_{4} or 2. G contains W_{5} or 3. G contains a spindle subgraph or 4. G is 3 -colorable. Hence, if we forbid additionally diamonds as induced subgraphs, we obtain the following corollary. Corollary 2 . Let G be a connected, (claw,diamond,net) -free graph. Then 1. G contains K_{4} or 2. G is 3 -colorable. Since spindle graphs have turned out to be a useful certificate for a graph not to be 3 -colorable, a natural question arises: If a graph G does not contain induced diamonds, what structural arguments can be given to describe that it is not 3 -colorable? The 3 -Colorability problem remains NP -complete for (claw,diamond,K_{4}) -free graphs ( [ 6 ] ). It has been also shown by [ 7 ] that 3 -colorability remains NP -complete for (claw,diamond, K_{4}, C_{4},C_{5},\ldots,C_{k}) -free graphs for any k\geq 4 . Using Beineke’s Theorem, which characterizes line-graphs in terms of nine forbidden induced subgraphs (cf. [BoM08]), it follows that (claw,diamond,K_{4}) -free graphs are line graphs of subcubic triangle-free graphs. Moreover, in graph coloring theory the following relationship for graphs and their line-graphs is well-known: Observation 3 . Let H be a graph and G=L(H) be its line graph. Then for every integer k\geq 1 it holds: G is k -colorable if and only if H is k -edge colorable. The class we are dealing with in this paper has been already studied by Munaro ( [ 8 ] ) resulting with theorems concerning independent sets and Hamiltonian problems. Our main motivation is an observation used by Munaro, providing that (claw,diamond) -free graphs are line graphs of subcubic triangle-free graphs. Theorem 4 . [ 8 ] The following statements are equivalent, for any graph G : 1. G is a (K_{4},claw,diamond) -free graph. 2. G is a line graph of a subcubic triangle-free graph. 3. G is a (1,1) -interval graph such that there do not exist four vertices sharing the same interval and there do not exist three vertices such that any two of them share a different interval. Thus, instead of 3 -colorability of (claw,diamond) -free graphs we will be working with an equivalent problem, that is, 3 -edge-colorability of subcubic triangle-free graphs. Note that a subproblem of the last problem is recognizing snarks , that is, simple, connected, bridgeless cubic graphs with girth at least five and chromatic index equal to four. It is true, since in the class of 3 -regular graphs contracting triangles and diamonds does not change edge-coloring properties. Not surprisingly, it was shown by Král’, Kratochvíl, Tuza, and Woeginger, that in the class considered by Munaro the 3 -Colorability problem is NP-complete ( [ 6 ] ). But which part of the class makes this problem hard? We are trying to answer this question, considering several subclasses. Interestingly, it seems that all hard-to-deal (claw,diamond) -free graphs contain an induced generalised net N_{i,j,k} . We will see that after excluding induced net, it is possible to easily determine, whether or not a graph of the considered class is 3 -colorable. In the Section 2.1 we will state and prove that if a (claw,diamond) -free graph does not contain an induced N_{1,1,3} , then it contains the complete graph K_{4} or the exceptional graph B_{10} (See Figure 2(c) ), or it is 3 -colorable. In Sections 2.2 and 2.3 similar theorems will be stated for (claw,diamond,N_{2,2,2}) -free graphs. Here, the list of exceptional graphs depends on whether or not a graph contains an induced cycle C_{5} . In Section 3 we gather conclusions and ask some further questions. Let us consider a connected, (claw,diamond) -free graph G . In the proofs of our theorems we will also assume without loss of generality that G is K_{4} -free. Then, by Theorem 4 we have that G=L(H) , where H is a subcubic triangle-free graph. Of course, a proper edge-coloring of H corresponds to proper vertex-coloring of G . Thus, we will work with simple, triangle-free graphs H with maximum degree bounded by 3 , and we will look for their proper edge-colorings. We will apply the following useful reductions for edge-colorings to these graphs. Reduction 1. If there is a vertex v\in V(H) such that d(v)=1 , then H is 3-edge-colorable if and only if H-v is 3-edge-colorable. So we can assume \delta(H)\geq 2 . Reduction 2. If we have two adjacent vertices u,v\in V(H) such that d(u)=d(v)=2 , then H is 3-edge-colorable if and only if H-u-v is 3-edge-colorable. So we can assume that no two vertices of degree 2 are adjacent. Reduction 3. Let C=w_{1}w_{2}w_{3}w_{4} be an induced 4 -cycle in H , where d(w_{1})=d(w_{3})=2 . Then H is 3-colorable if and only if H-\{w_{1},w_{2},w_{3},w_{4}\} is 3-edge-colorable. So we can assume H has no induced 4 -cycle with two independent vertices of degree 2 . Reduction 4. H does not contain cut-edges. Otherwise its line graph G=L(H) would contain a cut-vertex and could be reduced. The following easy observations characterize graphs which are necessarily non- 3 -edge-colorable. Let us recall that the matching number \alpha^{\prime}(H) of the graph H is a maximal cardinality of a set of independent edges in H . We say that H is overfull , if |E(H)|>\alpha^{\prime}(H)\Delta(H) . Observation 5 . If a graph H is overfull, then H is of Vizing class 2, so \chi^{\prime}(H)=\Delta(H)+1 . Observation 6 . Let H be a cubic bipartite graph and e\in E(H) . Let H^{*}(e) be a graph obtained from H by subdividing the edge e . Then \chi^{\prime}(H^{*}(e))=4 . Proof. Since H is cubic, we have |V(H)|=2k for some k . Moreover, \alpha^{\prime}(H)=k and we have \chi^{\prime}(H)=3 . For H^{*}(e) we have also \alpha^{\prime}(H^{*}(e))=k , but |E(H)|=3k+1 and by Observation 5 we have \chi(H^{*}(e))=4 . ∎ A simple example of a non- 3 -edge-colorable graph obtained this way is K_{3,3}^{*} - complete bipartite graph K_{3,3} with one edge (call it e ) subdivided. Trying to 3 -color edges of the graph K_{3,3}^{*} we obtain that both "halves" of e must receive the same color. We can use this observation to obtain a family D_{6i+1} of non- 3 -colorable graphs, joining i copies of K_{3,3} as depicted in Figure 2(a) . In a similar way (see Figure 2(b) ) we obtain a family D_{6i+5} . Line graphs (which are obviously non- 3 -vertex-colorable) of those families are called B_{9i+1} and B_{9i+7} , respectively - see Figures 2(c) and 2(d) . (a) D_{6i+1} (b) D_{6i+5} (c) B_{9i+1} (d) B_{9i+7} Figure 2 : The exceptional non- 3 -colorable, (claw,diamond) -free graphs and their base graphs. 2 Main results 2.1 The (claw, diamond, N 1,1,3 )-free graphs We use the name exceptional subgraph for graphs listed in statements of the theorems, satisfying the following condition: if a graph G of the considered class does not contain any of those subgraphs, then G is colorable with desired number k of colors. Of course, the clique K_{k} is always an exceptional subgraph. In this section we will show that for (claw,diamond,N_{1,1,3}) -free class there exists only one non-trivial exceptional subgraph. Theorem 7 . Let G be a connected, (claw,diamond) -free graph. If G is N_{1,1,3} -free, then 1. G contains K_{4} or 2. G contains B_{10} or 3. G is 3 -colorable. Proof. Let us assume that G does not contain K_{4} . Then G=L(H) , where H is some connected, subcubic, triangle-free graph, which does not contain a (not necessarily induced) S_{2,2,4} . Let us apply to H all the Reductions 1-4. We will show that • H=K_{3,3}^{*}=D_{7} or • H is 3 -edge-colorable. If \Delta(H)\leq 2 or H is bipartite, then \chi^{\prime}(H)\leq 3 . Hence, we can assume without loss of generality that we can find in G an induced odd cycle Q=v_{1}\ldots v_{p} , where p\geq 5 . Let us assume that p is minimal. We will distinguish two cases. Case 1: p\geq 7 Note that if N_{2}(Q)\neq\emptyset or if there is an edge non-adjacent to the cycle, then H contains an (induced or not) S_{2,2,4} . Thus, we conclude that Q is dominating and any vertex v\in N(Q) has at least 2 neighbors on Q . Now note that if the vertex v has two neighbors v_{i},v_{j}\in Q such that |i-j|\neq 2 , then we can find a shorter induced odd cycle, contradicting the minimality of p . Thus, for any v\in V(G)\setminus Q we have N_{Q}(v)=\{v_{i},v_{i+2}\} for some i . But if so, then by Reduction 3 one of vertices v,v_{i+1} must have an additional neighbor. From the previous steps we know that this neighbor does not belong to the cycle. So if N(Q) is non-empty, we can find a star S_{2,2,4} (see Figure 3 ). Figure 3 : Forbidden subgraph in Case 1 in the proof of Theorem 7 . Thus, in this case the graph H is an odd cycle without chords, so it is 3 -edge-colorable. Case 2: p=5 Note that if there exists a vertex v\in N_{3}(Q) adjacent to some u\in N_{2}(Q) , then by Reduction 1 the vertex v must have an additional neighbor u^{\prime}\neq u and we can find a star S_{2,2,4} (see Figure 4(a) ). Thus, N_{3}(Q)=\emptyset . Similarly, if there exists an edge uu^{\prime} , where u,u^{\prime}\in G[N_{2}] , then from triangle-freeness of H the vertices u,u^{\prime} must have two different neighbors v,v^{\prime}\in N_{1}(Q) and we can find S_{2,2,4} (see Figure 4(b) ). Thus, N_{2}(Q) is a set of isolated vertices. (a) (b) Figure 4 : Forbidden subgraphs in Case 2 of Theorem 7 . Let us consider a vertex w\in N_{2}(Q) . By Reduction 1 the vertex w has at least two neighbors v,v^{\prime} (where v,v^{\prime}\in N_{1}(Q) ). By Reduction 2 either d(w)=3 or d(v)=d(v^{\prime})=3 . If d(w)=3 , then N(w)=\{u,u^{\prime},u^{\prime\prime}\}\subset N_{1}(Q) and any vertex of N(w) has its private neighbor on Q (since \Delta(G)<4 ). If the three private neighbors are consecutive, we can easily find S_{2,2,4} (see Figure 5(a) ), so suppose otherwise. If G=Q\cup\{w,u,u^{\prime},u^{\prime\prime}\} , then H is easily 3 -edge-colorable (see Figure 5(b) ). But if there is more vertices, then there must be a vertex z adjacent either to some vertex v_{i} of Q (where v_{i} is not a neighbor of u,u^{\prime},u^{\prime\prime} ) or to some vertex of \{u,u^{\prime},u^{\prime\prime}\} . In both cases we can find S_{2,2,4} (see Figure 5(c) ). (a) (b) (c) Figure 5 : Forbidden subgraphs and coloring of neighborhood of C_{5} in Case 2 of Theorem 7 . Hence, we may assume d(w)=2 and d(u)=d(u^{\prime})=3 , that is, u,u^{\prime} have additional neighbors v and v^{\prime} respectively. If v\notin Q or v^{\prime}\notin Q , we can find S_{2,2,4} (see Figure 6(a) ). Otherwise we have G=Q\cup\{w,u^{\prime},u^{\prime\prime}\} and G is 3 -edge-colorable (see Figure 6(b) ). (a) (b) (c) Figure 6 : Forbidden subgraphs and coloring of neighborhood of C_{5} in Case 2 of Theorem 7 . Thus, we can assume N_{2}(Q)=\emptyset . Let us consider N(Q) . If N(Q) contains two disjoint edges xx^{\prime} and yy^{\prime} , then we can always find two vertices v_{i},v_{i+2}\in Q adjacent to xx^{\prime},yy^{\prime} respectively and we have S_{2,2,4} . So N(Q) is 2K_{2} -free. Suppose |N(Q)|\geq 4 . Then at least three vertices have only one neighbor on Q , so there are at least two edges in N(Q) (since \delta(G)>1 ). So, since N(Q) is 2K_{2} -free, it does contain P_{3} and at least one isolated vertex w . Note that without loss of generality there exists i such that w is adjacent to v_{i},v_{i+2}\in Q . Whether some end-vertex of P_{3} is adjacent to v_{i+1} or not, we can always find S_{2,2,4} (see Figure 6(c) ). Thus, |N(Q)|\leq 3 and N(Q) is isomorphic to some subgraph of P_{3} . Note that if H does not contain K^{*}_{3,3} (see Figure 7(a) ), then it is a subgraph of one of 3 -edge-colorable graphs depicted in Figures 7(b) and 7(c) . It is trivial if |H|\leq 7 , so suppose |H|=8 and H is maximal in the sense that adding another vertex or another edge would destroy one of properties of H (triangle-freeness, subcubicidity, minimality with respect to Reductions). If N(Q) contains an isolated vertex, then (since K^{*}_{3,3}\nleq H ) we can always add in N(Q) an edge between the isolated vertex and one of the remaining ones, which contradicts the maximality of H . Thus, H[N(Q)] is isomorphic to P_{3} . If both end-vertices of the path P_{3} are of degree 1 on the cycle, then there are no more than 3 edges between Q and N(Q) and the graph is not maximal. Thus, one endvertex is adjacent to two vertices of Q , say v_{1} and v_{3} . If the second endvertex is adjacent to v_{2} , H^{\prime} is isomorphic to the 3 -edge-colorable graph depicted in Figure 7(b) . Otherwise, from the triangle-freeness of H^{\prime} , the second endvertex has degree 1 on the cycle, and from the maximality of H^{\prime} , the middle vertex is adjacent to v_{2} . Thus, H^{\prime} is isomorphic to the graph depicted in Figure 7(c) . (a) (b) (c) Figure 7 : Possible neighborhood of C_{5} and its coloring in Case 2 of Theorem 7 . ∎ 2.2 The (claw, diamond, N 2,2,2 )-free graphs without short cycles In this section we will prove that for the class of (claw,diamond,N_{2,2,2},C_{5}) -free graphs we have only two families of exceptional graphs. It is the first part of analysis of the (claw,diamond,N_{2,2,2}) -free class. In the next subsection, a similar theorem will be stated for (claw,diamond,N_{2,2,2}) -free graphs containing C_{5} . Theorem 8 . Let G be a connected, (claw,diamond) -free graph. If G is also (N_{2,2,2},C_{5}) -free, then 1. G contains K_{4} or 2. G contains B_{9i+1} for some i\geq 1 or 3. G contains B_{9i+7} for some i\geq 1 or 4. G is 3 -colorable. In fact, Theorem 8 will follow as a corollary from the more specific theorem below. Theorem 9 . Let H be a connected, subcubic triangle-free graph, minimal with respect to the Reductions 1-4. If H is also (S_{3,3,3},C_{5}) -free, then 1. H is isomorphic to D_{6i+1} for some i\geq 1 or 2. H is isomorphic to D_{6i+5} for some i\geq 1 or 3. H is 3 -edge-colorable. Proof. If H is bipartite, then \chi^{\prime}(H)=\Delta(H) , so let us assume otherwise and consider the shortest induced odd cycle Q=v_{1}\ldots v_{p} . Since H is C_{5} -free, we have p\geq 7 . Of course, N_{3}(Q)=\emptyset , since otherwise we can easily find S_{3,3,3} . Suppose now u\in N_{2}(Q) and v\in N_{1}(Q) is a neighbor of u . But u must have another neighbor v^{\prime}\neq v (by Reduction 1 and triangle-freeness of H ) and in the graph Q\cup{v,u,v^{\prime}} we can easily find a star S_{3,3,3} . Thus, N_{2}(Q)=\emptyset . By the same argument we have that N(Q) is P_{3} -free. Since Q is a shortest cycle in H , then for every w\in N(Q) we have d_{Q}(w)\leq 2 . Moreover, if d_{Q}(w)=2 , then N_{Q}(w)=\{v_{i},v_{i+2}\} for some i , and if ww^{\prime}\in E(H) for some w^{\prime}\in N(Q) , then N_{Q}(\{w,w^{\prime}\})\subset\{v_{i},\ldots,v_{i+3}\} for some i . Thus, the graph H is a necklace of following gadgets (note that by Reductions 2 and 3 every gadget must contain at least 2 vertices from N(Q) and one of those vertices must have two neighbors on the cycle): (a) (b) (c) (d) Figure 8 : Gadgets of graph H in the proof of Theorem 7 . Note that gadgets (b) and (c) admit coloring with the same colors on the end-edges and different as well. Gadget (a) admits only colorings with the same colors on the end-edges and (d) - only with different colors. Thus, if H is non- 3 -edge-colourable, it can contain only (a) gadgets and at most one (d) gadget. Moreover, the cycle can contain no more than 1 vertex not belonging to any gadget, and if it contains such a vertex, then it does not contain a gadget (d) . This leaves us with two possibilities only - a necklace of gadgets (a) with one edge subdivided (family D_{6i+1} ) and a necklace of gadgets (a) and one gadget (d) (family D_{6i+5} ). This finishes the proof of Theorem 9 . ∎ 2.3 The (claw, diamond, N 2,2,2 )-free graphs containing C_{5} In the main proof of this subsection we will be using several technical edge-coloring lemmas. The first lemma provides an algorithm coloring edges of a Hamiltonian graphs satisfying at least one of additional conditions. Lemma 10 . Let H be a connected, Hamiltonian, subcubic graph and let v_{1}\ldots v_{2p+1} be the Hamiltonian cycle. If 1. there is an edge v_{i}v_{j}\in E(G) such that |i-j|>1 and d(v_{i-1})=d(v_{j-1})=2 or 2. there is an edge v_{i}v_{j}\in E(G) such that |i-j|>1 and d(v_{i+1})=d(v_{j+1})=2 or 3. there is i\in[2p+1] such that d(v_{i-1})=d(v_{i+1})=2 , then \chi^{\prime}(G)=3 . Proof. Cases 1. and 2. Without loss of generality we have d(v_{i-1})=d(v_{j-1})=2 and j=i+2n (the other situations are symmetric). We will start with precoloring the graph H : we color with red all the chords and the edge v_{i-1}v_{i} , and the rest of the cycle with green and blue alternately, starting from v_{i}v_{i+1} . The only color conflict is caused in v_{i} by chord v_{i}v_{j} . So we change colors on the red/blue-path starting from this chord. Note that this path ends in v_{j-1} , because j=i+2n . Case 3. We start with precoloring as in the previous case. If there is no chord in the vertex v_{i} , we are done. Otherwise we change colors on the red/blue-path starting from this chord. If it ends in some vertex v\neq v_{i-1} , we are done also. But if it ends in vertex v_{i-1} , we still have color conflict, because edges v_{i-2}v_{i-1} and v_{i-1}v_{i} are both colored with red. Then we recolor v_{i-1}v_{i} with green and v_{i}v_{i+1} with red, obtaining a proper coloring. (a) Precoloring in Cases 1. and 2. (b) Precoloring in Case 3. Figure 9 : Precoloring used by the algorithm in Lemma 10 . ∎ The next lemma allows us to color the edges of a near-Hamiltonian graphs. Lemma 11 . Let H be a connected, subcubic, triangle-free graph, and let v\in(G) be such a vertex that d(v)=2 and G-v has Hamiltonian cycle v_{1}\ldots v_{2p} . Let v_{i},v_{j} , where |i-j|\geq 2 , be the neighbors of v on the cycle. If 1. one of the vertices v_{i-1},v_{i+1},v_{j-1},v_{j+1} is of degree 2 or 2. there is a chord v_{i-1}v_{l} such that either v_{l+1} is of degree 2 , or such that v_{l-1} is of degree 2 and |i-l|=2n (for some n\in\mathbb{N} ) or 3. there is a chord v_{i+1}v_{l} such that either v_{l-1} is of degree 2 , or such that v_{l+1} is of degree 2 and |i-l|=2n (for some n\in\mathbb{N} ), then \chi^{\prime}(G)=3 . Proof. Case 1. Suppose v_{i+1} is of degree 2 . We color v_{i}v_{i+1} with red and the rest of cycle alternately with green and blue. Then we can color vv_{j} and the chords of the cycle with red and vv_{i} with blue without color conflict (see Figure 10(a) ). In other cases the coloring is analogous. Cases 2 and 3. Suppose there exists a chord v_{i+1}v_{l} and v_{l-1} is of degree 2 . We color v_{i}v_{i+1},v_{l}v_{l-1} with red and v_{i+1}v_{l} with blue. Then we can - without color conflict - color the rest of the cycle alternately with blue and green, vv_{j} and the rest of chords with red, and vv_{i} with remaining color. In other cases the coloring is analogous. (a) Case 1. (b) Cases 2 and 3. Figure 10 : Coloring in the proof of Lemma 11 . ∎ In the case considered in this Section, the set of non-trivial exceptional graphs is more varied. It contains the graph B_{10} , a line graph of P^{*} , and line graphs of all subcubic 9 -cycles with four chords. It is easy to observe that all graphs of the last group are overfull. As before, the alternative stated in the theorem can be read as necessary and sufficient conditions for 3 -colorability of a (claw,diamond,N_{2,2,2}) -free graph containing a cycle C_{5} . Here, the graph P^{*} is the Petersen graph with one vertex deleted. Theorem 12 . Let G be a connected, (claw,diamond,N_{2,2,2}) -free graph. If G contains an induced C_{5} , then 1. G contains K_{4} or 2. G contains B_{10} or 3. G contains L(P^{*}) or 4. G contains a line graph of an overfull graph H consisting of an odd cycle C_{9} with 4 chords or 5. G is 3 -colorable. Theorem 12 will follow as a corollary from Theorem 13 . Theorem 13 . Let H be a connected, triangle-free subcubic graph, minimal with respect to Reductions 1-4. If H is also S_{3,3,3} -free and H contains an induced C_{5} , then 1. H is isomorphic to D_{7} or 2. H is isomorphic to P^{*} or 3. H is an overfull graph consisting of an odd cycle C_{9} with 4 chords or 4. H is 3 -edge-colorable. Proof. By assumption, H contains a 5 -cycle Q=v_{1}v_{2}v_{3}v_{4}v_{5} . By Reduction 4 every component of H-Q is connected to Q with at least 2 edges. Thus, we have at most 2 components. Suppose now one of those components is an isolated vertex \{w\} . Then there exists such an index i that the vertex w is adjacent to v_{i-1} and to v_{i+1} . But then by the Reduction 3 there must be a vertex u outside the cycle, adjacent to v_{i} , and without loss of generality we can take the 5 -cycle Q\setminus\{v_{i}\}\cup\{w\} and consider a component consisting of at least v_{i} and u . So we will assume that any component has at least one edge. Note that to find an S_{3,3,3} it is sufficient to find one of the subgraphs depicted in Figure 11 . (a) (b) (c) Figure 11 : Subgraphs occurring in the graphs considered in Case 1 of the proof of Theorem 12 . Case 1. |V(H)|\geq 10 . Recall that by Reductions each component of H-Q is connected to Q with at least 2 edges and there are no vertices of degree 1. If we have 2 components, say C_{1},C_{2} , such that |C_{1}|\leq|C_{2}| , then by the assumptions 2\leq|C_{1}|,3\leq|C_{2}| , and we can always find a S_{3,3,3} (see Figure 11(a) ). Thus, the graph H-Q is connected. Let us consider the maximum degree \Delta(H-Q) . If we have \Delta(H-Q)=2 and H-Q is a cycle, then we always can find a subgraph 11(a) . If \Delta(H-Q)=2 and G-Q is a path, we always have one of subgraphs 11(a) or 11(b) , except when H-Q is a path of length 5 and v_{1},v_{2} are adjacent to its second and fourth vertex. But then by Reduction 1 both end-vertices of the path must be adjacent to the cycle and we can find another i such that v_{i},v_{i+1} are adjacent to the path (so we can find a subgraph 11(a) ). If \Delta(H-Q)=3 , then there exists a spanning tree T of H-Q containing a star S_{1,1,2} . Let the vertex of degree 3 of the star be a root of the tree T . Note that if we join two consecutive vertices v_{1},v_{2} with this spanning tree, we always obtain a subgraph 11(a) , except when v_{1},v_{2} are joined with two leaves of the same parent or when they are joined with a leaf and its parent. Suppose v_{1},v_{2} are adjacent to two leaves u_{1},u_{2} of the same parent u in T . If u_{1} or u_{2} is not of degree 1 in H-Q , then we always can find a subgraph 11(a) , since from triangle-freeness of H the vertex u must have a parent (or another child, if u is a root) non-adjacent to u_{1},u_{2} . If both u_{1} , u_{2} are of degree 1 in H-Q , then there always exist a path P=uvv^{\prime} starting from u , such that u_{1},u_{2}\notin P . Then whether v^{\prime} is adjacent to u_{1},u_{2} , to the cycle or to another vertex of H-Q , we can always find one of the subgraphs 11(a) or 11(c) . Suppose now v_{1},v_{2} are adjacent to the leaf u and its parent u^{\prime} . Then either we can find a subgraph 11(b) or T=S_{1,1,2} , where u and u^{\prime} belong to the only one subdivided edge of the star. If one of the other leaves of T is adjacent to u , we have a subgraph 11(a) . Otherwise the other leaves are adjacent to Q and we can find another i such that v_{i} , v_{i+1} are end-vertices of disjoint P_{3} and P_{4} as depicted in 11(a) . Case 2. |V(H)|=9 Note that H-Q is a path P_{4} , a cycle C_{4} or a star K_{1,3} . If H-Q is a cycle, then by Reductions 2 and 3 there are at least 3 edges between Q and H-Q . Thus, we can always find a 9 -cycle. By Lemma 10 we know that H is either an overfull graph of 13 edges or is a P^{*} , or is 3 -edge-colorable. If H-Q is a star K_{1,3} , then by Reduction 1 all three leaves of H-Q must be adjacent to Q . Since \Delta(H)\leq 3 , at least one of the leaves has only one neighbor on the cycle. Whether there are 2 , 1 or 0 leaves with degree 2 on the cycle, we can always find a 8 -cycle Q^{\prime} formed by Q , two leaves and the center of the star, such that the remaining leaf has degree 2 on Q^{\prime} . Then we can use Lemma 11 . Since the length of the cycle is 8 , one of cases 1,2,3 of Lemma 11 always occurs, so the graph is 3 -edge-colorable. If H-Q is a path P_{4}=u_{1}\dots u_{4} , then by Reduction 1 both end-vertices must be adjacent to Q . If they are adjacent to two consecutive vertices of the cycle Q , then we can easily find C_{9} and we use Lemma 10 as before, so assume otherwise - without loss of generality u_{1}v_{1},u_{4}v_{3}\in E(H) . Since H is triangle-free, we have d(u_{1})=d(u_{4})=2 . By Reduction 2 both vertices u_{2},u_{3} must be adjacent to the cycle Q . If one of them is adjacent to v_{2} , then we can find an 8 -cycle containing Q and three vertices of P_{4} , where remaining end-vertex is of degree 2; if not, there is an 8 -cycle containing P_{4} and four vertices of Q , where remaining vertex, v_{2} , is of degree 2. Then we use Lemma 11 as before. Case 3. |V(H)|\leq 8 If |V(H)|\leq 8 , then H is S_{2,2,4} -free, so L(H) is N_{1,1,3} -free. Then the claim follows as a corollary from Theorem 7 . ∎ 3 Further work Recall, that Lozin and Purcell [ 7 ] have shown that the 3 -colorability problem remains NP -complete even for the class of (claw,diamond,K_{4},C_{4},C_{5},\ldots C_{k}) -free graphs for any integer k\geq 4. Let us note that since obviously Reductions 1-4 can be applied in polynomial time, the following corollary results from Theorems 9 and 13 . Corollary 14 . Let H be a connected, triangle-free subcubic graph. If H is also S_{3,3,3} -free, then there is a polynomial algorithm deciding whether or not H is 3 -edge-colorable. Every graph different from K_{3} and K_{1,3} is uniquely determined by its line graph and can be restored from this line graph in polynomial time, so we can also state the following. Corollary 15 . Let G be a connected, (claw,diamond) -free graph. If G is also N_{2,2,2} -free, then there is a polynomial algorithm deciding whether or not G is 3 -colorable. Moreover, we show that there are only finitely many non 3 -colorable N_{1,2,k} -graphs for any k\geq 2 , but there exist infinitely many non 3 -colorable N_{i,j,k} -graphs for any 2\leq i\leq j\leq k. Theorem 16 . Let G be a (claw,diamond,N_{1,2,k}) -free graph with an integer k\geq 2 . If n>(k+4)(2^{k}+1)+1 , then 1. G contains K_{4} or 2. G is 3 -colorable. Proof. Suppose G contains no K_{4}. Following previous discussions and reductions we may assume 3\leq\delta(G)\leq\Delta(G)=4. If G is perfect, then \chi(G)=\omega(G)\leq 3 and so G is 3 -colorable. Hence we may assume that G is not perfect. Since G is diamond-free, G does not contain an induced odd antihole of size at least seven. Hence we may further assume that G contains an odd hole Q=v_{1}v_{2}\ldots v_{p} of order p\geq 5. Then N^{1}(Q)\neq\emptyset since \delta(G)\geq 3. If w\in N^{1}(Q) then there are four consecutive vertices v_{i},v_{i+1},v_{i+2},v_{i+3} with v_{i+1}v_{i+2}\in E(G) and v_{i}v_{i+3}\notin E(G), since G is (claw,diamond) -free. If N_{Q}(w)=\{v_{i},v_{i+1},v_{j},v_{j+1}\} for two integers with 1\leq i(k+4)(2^{k}+1)+1 we conclude that p\geq k+5. Now, if N^{2}(Q)\neq\emptyset, then there is an induced N_{1,2,k}, a contradiction. Hence, we may assume that N^{2}(Q)=\emptyset. Since \delta(G)\geq 3 it follows that N(w_{i})\cap N^{1}(Q)\neq\emptyset. Since Q is a shortest odd hole we deduce that N(w_{i})\cap N^{1}(Q)\subset\{w_{i-2},w_{i+2}\}. If N(w_{i})\cap N^{1}(Q)=\{w_{i-2},w_{i+2}\}, then there is a claw, a contradiction. Hence, we may assume that G[N^{1}(Q)] is an induced matching. Now, we 3 -color Q as follows: If p\equiv 0(mod\ 3) then we color v_{1},v_{2},v_{3},\ldots alternatingly by 1,2,3,\ldots. If p\equiv 1(mod\ 3) then we color v_{1},v_{2},v_{3},\ldots by 1,2,1,3 and then alternatingly by 1,2,3,\ldots. If p\equiv 2(mod\ 3) then we color v_{1},v_{2},v_{3},\ldots by 1,2,1,3,1,2,1,3 and then alternatingly by 1,2,3,\ldots. Next, observe that \{c(v_{i}),c(v_{i+1})\}\neq\{c(v_{i+2}),c(v_{i+3})\} for 1\leq i\leq p. Therefore, we can extend the 3 -coloring of Q with two suitable colors to a 3 -coloring of Q for every edge w_{i}w_{i+2}. So, we obtain a 3 -coloring of the whole graph G. ∎ Thus, we can state the following corollary. Corollary 18 . Let G be a (claw,diamond,N_{1,2,k}) -free graph. Then there is a polynomial algorithm deciding whether or not G is 3 -colorable. Let us recall that the non- 3 -colorable, infinite families of graphs B_{9i+1} and B_{9i+7} are (claw,diamond,N_{2,2,2}) -free. Thus, we can state the following. Corollary 19 . Let 2\leq i\leq j\leq k . Then there exist infinitely many non- 3 -colorable, (claw,diamond,N_{i,j,k}) -free graphs not containing the complete graph K_{4} . Corollary 20 . Let G be a (claw,diamond,N_{1,2,k}) -free graph with 2\leq k . Then there are only finitely many non- 3 -colorable graphs not containing K_{4} .