The 6th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2007) was held at the University of Twente, The Netherlands, 29-31 May, 2007. The CTW started as a series of biennial meetings at the Universities of Cologne in Germany and Twente in the Netherlands. Ever increasing interest has turned the CTW into a now annual event with the Politecnico di Milano, the University of Duisburg-Essen, the Universit degli Studi di Milano, and Ecole Polytechnique in Paris as additional partners. The scope of the workshop comprises the theory and applications of discrete algorithms, graphs, and combinatorial structures in the wide sense. After the workshop, the participants and the research community at large were invited to submit research articles relating to the themes of the workshop. As guest editors, we are pleased to present a collection of articles that were selected from the submissions by the refereeing process. We thank all the contributors for making it so easy to document the workshop and the state-of-the-art with interesting articles and we hope that you, the reader, will find these contributions stimulating as well.