| 2006 | A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs. Serge Gaspers, Mathieu Liedloff |
| 2006 | A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators. Christian Knauer, Andreas Spillner |
| 2006 | A Fully Dynamic Algorithm for the Recognition of Stavros D. Nikolopoulos, Leonidas Palios, Charis Papadopoulos |
| 2006 | An Implicit Representation of Chordal Comparabilty Graphs in Linear-Time. Andrew R. Curtis, Clemente Izurieta, Benson L. Joeris, Scott M. Lundberg, Ross M. McConnell |
| 2006 | Approximating the Traffic Grooming Problem in Tree and Star Networks. Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, Shmuel Zaks |
| 2006 | Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions. Bodo Manthey |
| 2006 | Bounded Arboricity to Determine the Local Structure of Sparse Graphs. Gaurav Goel, Jens Gustedt |
| 2006 | Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs. Haim Kaplan, Yahav Nussbaum |
| 2006 | Chordal Deletion Is Fixed-Parameter Tractable. Dániel Marx |
| 2006 | Circular-Perfect Concave-Round Graphs. Sylvain Coulonges |
| 2006 | Clique Graph Recognition Is NP-Complete. Liliana Alcón, Luérbio Faria, Celina M. H. de Figueiredo, Marisa Gutierrez |
| 2006 | Computing Graph Polynomials on Graphs of Bounded Clique-Width. Johann A. Makowsky, Udi Rotics, Ilya Averbouch, Benny Godlin |
| 2006 | Convex Drawings of Graphs with Non-convex Boundary. Seok-Hee Hong, Hiroshi Nagamochi |
| 2006 | Divide-and-Color. Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith |
| 2006 | Finding Intersection Models of Weakly Chordal Graphs. Martin Charles Golumbic, Marina Lipshteyn, Michal Stern |
| 2006 | Flexible Matchings. Miklós Bartha, Miklós Krész |
| 2006 | Generalised Dualities and Finite Maximal Antichains. Jan Foniok, Jaroslav Nesetril, Claude Tardif |
| 2006 | Generation of Graphs with Bounded Branchwidth. Christophe Paul, Andrzej Proskurowski, Jan Arne Telle |
| 2006 | Graph Labelings Derived from Models in Distributed Computing. Jérémie Chalopin, Daniël Paulusma |
| 2006 | Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers Fedor V. Fomin |
| 2006 | Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms. Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien de Montgolfier |
| 2006 | How to Sell a Graph: Guidelines for Graph Retailers. Alexander Grigoriev, Joyce van Loon, René Sitters, Marc Uetz |
| 2006 | Improved Edge-Coloring with Three Colors. Lukasz Kowalik |
| 2006 | Listing Chordal Graphs and Interval Graphs. Masashi Kiyomi, Shuji Kijima, Takeaki Uno |
| 2006 | Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy. Jirí Fiala, Jan Kratochvíl |
| 2006 | Minimal Proper Interval Completions. Ivan Rapaport, Karol Suchan, Ioan Todinca |
| 2006 | Monotony Properties of Connected Visible Graph Searching. Pierre Fraigniaud, Nicolas Nisse |
| 2006 | Partitioned Probe Comparability Graphs. David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng |
| 2006 | Simultaneous Graph Embeddings with Fixed Edges. Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz |
| 2006 | Strip Graphs: Recognition and Scheduling. Magnús M. Halldórsson, Ragnar K. Karlsson |
| 2006 | Treewidth: Characterizations, Applications, and Computations. Hans L. Bodlaender |
| 2006 | Vertex Coloring of Comparability+ Yasuhiko Takenaga, Kenichi Higashide |