<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Minimal Classes of Graphs of Unbounded Clique-Width
Vadim V. Lozin
DIMAP & Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK
Annals of Combinatorics 15 (4) pp.707-722 December, 2011
AMS Subject Classification: 05C75
In the present paper, we identify the first two minimal with respect to set-inclusion hereditary classes of graphs of unbounded clique-width: Bipartite permutation graphs and unit interval graphs.
Keywords: clique-width; bipartite permutation graphs; unit interval graphs; fixed parameter tractability


1.Asdre, K., Nikolopoulos, S.D.: NP-completeness results for some problems on subclasses of bipartite and chordal graphs. Theoret. Comput. Sci. 381(1-3), 248–259 (2007)

2. Chandran, L.S., Lozin, V.V., Subramanian, C.R.: Graphs of low chordality. DiscreteMath. Theor. Comput. Sci. 7(1), 25–35 (2005)

3. Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R.: The strong perfect graph theorem. Ann. of Math. (2) 164(1), 51–229 (2006)

4. Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach. 41(1), 153–180 (1994)

5. Brandstädt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Combin. 67, 273–281 (2003)

6. Brandst¨adt, A., Engelfriet, J., Le, H.-O., Lozin, V.V.: Clique-width for 4-vertex forbidden subgraphs. Theory Comput. Syst. 39, 561–590 (2006)

7. Bodlaender, H.L., Kloks, T., Niedermeier, R.: Simple MAX-CUT for unit interval graphs and graphs with few P4s. Electron. Notes Discrete Math. 3, 19–26 (1999)

8. Bogart, K.P., West, D.B.: A short proof that “roper = unit”. Discrete Math. 201(1-3), 21–23 (1999)

9. Chang, R.-S.: Jump number maximization for proper interval graphs and series-parallel graphs. Inform. Sci. 115(1-4), 103–122 (1999)

10. Chen, C., Chang, C.-C., Chang, G.J.: Proper interval graphs and the guard problem. Discrete Math. 170(1-3), 223–230 (1997)

11. Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)

12. Courcelle, B., Olariu, S.: Upper bounds to the clique-width of graphs. Discrete Appl. Math. 101, 77–114 (2000)

13. de Figueiredo, C.M.H., Meidanis, J., de Mello, C.P., Ortiz, C.: Decompositions for the edge colouring of reduced indifference graphs. Theoret. Comput. Sci. 297(1-3), 145–155 (2003)

14. Demaine, E.D., Hajiaghayi, M.T.: Diameter and treewidth in minor-closed graph families, revisited. Algorithmica 40(3), 211–215 (2004)

15. Diestel, R.: Graph Theory, 3rd Ed. Graduate Texts in Mathematics, 173. Springer-Verlag, Berlin (2005)

16. Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27(3-4), 275–291 (2000)

17. Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width Minimization is NP-hard [extended abstract]. In: Kleinberg, J.M. (Ed.) STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 354–362. ACM, New York (2006)

18. Fishburn, P.C.: An interval graph is not a comparability graph. J. Combin. Theory 8(4), 442–443 (1970)

19. Fouquet, J.-L., Giakoumakis, V.: On semi-P4-sparse graphs. Discrete Math. 165/166, 277–300 (1997)

20. Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Internat. J. Found. Comput. Sci. 11(3), 423–443 (2000)

21. Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23(4), 613–632 (2003)

22. Hammer, P.L., Peled, U.N., Sun, X.: Difference graphs. Discrete Appl.Math. 28(1), 35-44 (1990)

23. Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput. 31(1), 289–305 (2001)

24. Jean, M.: An interval graph is a comparability graph. J. Combin. Theory 7(2), 189–190 (1969)

25. Kaplan, H., Shamir, R.: Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM J. Comput. 25(3), 540–561 (1996)

26. Kloks, T., Kratsch, D., Müller, H.: Bandwidth of chain graphs. Inform. Process. Lett. 68(6), 313–315 (1998)

27. Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed cliquewidth. Discrete Appl. Math. 126(2-3), 197–221 (2003)

28. Lozin, V.V., Rautenbach, D.: On the band-, tree- and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18(1), 195–206 (2004)

29. Lozin, V.V., Rautenbach, D.: Chordal bipartite graphs of bounded tree- and clique-width. Discrete Math. 283(1-3), 151–158 (2004)

30. Lozin, V.V., Rudolf, G.: Minimal universal bipartite graphs. Ars Combin. 84, 345–356 (2007)

31. Lozin, V.V., Volz, J.: The clique-width of bipartite graphs in monogenic classes. Internat. J. Found. Comput. Sci. 19(2), 477–494 (2008)

32. Makowsky, J.A., Rotics, U.: On the clique-width of graphs with few P4’s. Internat. J. Found. Comput. Sci. 10(3), 329–348 (1999)

33. Marx, D.: Precoloring extension on unit interval graphs. Discrete Appl. Math. 154(6), 995–1002 (2006)

34. Oum, S.-i.: Approximating rank-width and clique-width quickly. In: Kratsch, D. (ed.) Graph-Theoretic Concepts in Computer Science. Lecture Notes in Comput. Sci.Vol. 3787, pp. 49–58. Springer, Berlin (2005)

35. Roberts, F.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 139–146. Academic Press, New York (1969)

36. Robertson, N., Seymour, P.D.: Graph minors. V. excluding a planar graph. J. Combin. Theory Ser. B 41(1), 92–114 (1986)

37. Spinrad, J., Brandstädt, A., Stewart, L.: Bipartite permutation graphs. Discrete Appl. Math. 18(3), 279–292 (1987)

38. Srikant, R., Sundaram, R., Sher Singh, K., Rangan, C.P.: Optimal path cover problem on block graphs and bipartite permutation graphs. Theoret. Comput. Sci. 115(2), 351–357 (1993)