A Characterization of Graphs with Vertex Cover Six

1. S. Arnborg, A. Proskurowski, and D. Seese. Monadic second order logic, tree automata and forbidden minors. In Proceedings of the 4th Workshop on Computer Science Logic, CSL’90, volume 533 of Lecture Notes on Computer Science, pages 1–16. Springer-Verlag, 1991.

   Google Scholar 

2. R. Balasubramanian, M. R. Fellows, and V. Raman. An improved fixed-parameter algorithm for vertex-cover. Information Processing Letters, 65(3):163–168, 1998.

   Article  MathSciNet  Google Scholar 

3. K. Cattell and M. J. Dinneen. A characterization of graphs with vertex cover up to five. In V. Bouchitte and M. Morvan, Eds, Orders, Algorithms and Applications, ORDAL’94, volume 831 of Lecture Notes on Computer Science, pages 86–99. Springer-Verlag, July 1994.

   Google Scholar 

4. K. Cattell, M. J. Dinneen, R. G. Downey, M. R. Fellows, and M. A. Langston. On computing graph minor obstruction sets. Theoretical Computer Science, 233(1–2):107–127, February 2000.

   Google Scholar 

5. M. J. Dinneen and L. Xiong. The minor-order obstructions for the graphs of vertex cover six. Research Report CDMTCS-118, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, Auckland, New Zealand, 29 pp. January 2000. (http://www.cs.auckland.ac.nz/CDMTCS/researchreports/118vc6.pdf)

   Google Scholar 

6. M. R. Fellows and M. A. Langston. An analogue of the Myhill-Nerode Theorem and its use in computing finite-basis characterizations. In IEEE Symposium on Foundations of Computer Science Proceedings, volume 30, pages 520–525, 1989.

   Article  Google Scholar 

7. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979.

   Google Scholar 

8. P. Hall. On representation of subsets. J. London Math. Soc., 10:26–30, 1935.

   Article  MATH  Google Scholar 

9. J. Lagergren and S. Arnborg. Finding minimal forbidden minors using a finite congruence. In Proceedings of the International Colloquium on Automata, Languages and Programming, volume 510 of Lecture Notes on Computer Science, pages 533–543. Springer-Verlag, 1991. 18th ICALP.

   Google Scholar 

10. B. D. McKay. nauty User’s Guide (version 2.0). Tech Report TR-CS-90-02, Australian National University, Department of Computer Science, 1990.

    Google Scholar 

11. A. Proskurowski. Graph reductions, and techniques for finding minimal forbidden minors. In N. Robertson and P. D. Seymour, Eds, Graph Structure Theory, volume 147 of Contemporary Mathematics, pages 591–600. American Mathematical Society, 1993.

    Google Scholar 

12. N. Robertson and P. D. Seymour. Graph Minors-A survey. In Surveys in Combinatorics, volume 103, pages 153–171. Cambridge University Press, 1985.

    MathSciNet  Google Scholar 

Download references