Discrete Mathematics & Theoretical Computer Science

In 2015 DMTCS migrates to http://dmtcs.episciences.org/ on the Episciences platform:

  • All open submissions will continued on the server where they were first submitted.
  • All existing volumes will be migrated to the new platform.
  • This server here will eventually be discontinued.

Warning: This server is closed for submissions. Only submissions that had originally submitted here are still managed on this server. Please refer to the new server for submission of new work.

The current volumes of DMTCS are

  • 17:2, regular issue, publication is ongoing.
  • on our new server: 18:1, regular issue, publication is ongoing.


  • Analysis of Algorithms
  • Automata, Logic and Semantics
  • Combinatorics
  • Discrete Algorithms
  • Distributed Computing and Networking
  • Graph Theory

The journal is devoted to a quest of quality and immediacy. The median value for acceptance of papers (including refereeing and all eventual revisions) has been about 12 month for papers submitted in 2011.

Author's manuscripts are published as soon as they have been accepted and the authors provide the final LaTeX sources, They are freely available via the Internet. Due to the combined efforts of our authors (who typeset their final document with our LaTeX style) and our volunteers (who do the final layout) the time between reception of the sources and final publication has a median of 2 weeks.

DMTCS is published by a French association of the same name in cooperation with the Laboratoire Lorrain de Recherche en Informatique et ses Applications, LORIA, in Nancy, France, which provides us with our primary server.

Vol 17, No 2 (2015)

Table of Contents

Automata, Logic and Semantics

Classical Automata on Promise Problems PDF
Viliam Geffert, Abuzer Yakaryilmaz 157-180


Minimum Number of Colors: the Turk’s Head Knots Case Study PDF PostScript
Pedro Lopes, Joao Matias 1-30
On avoidance of patterns of the form σ-τ by words over a finite alphabet PDF
Toufik Mansour, Mark Shattuck 181-202
Symmetries of Monocoronal Tilings PDF
Dirk Frettlöh, Alexey Garber 203-234

Discrete Algorithms

Improving Vertex Cover as a Graph Parameter PDF
Robert Ganian 77-100
Reducing the rank of a matroid PDF
Gwenaël Joret, Adrian Vetta 143-156

Graph Theory

The game chromatic number of trees and forests PDF PostScript
Charles L Dunn, Victor Larsen, Kira Lindke, Troy Retter, Dustin Toci 31-48
On graphs double-critical with respect to the colouring number PDF
Matthias Kriesell, Anders Sune Pedersen 49-62
The complexity of P4-decomposition of regular graphs and multigraphs PDF
Ajit A. Diwan, Justine E. Dion, David J. Mendell, Michael J. Plantholt, Shailesh K. Tipnis 63-76
Disimplicial arcs, transitive vertices, and disimplicial eliminations PDF
Martiniano Roberto Eguía, Francisco Juan Soulignac 101-118
Packing Plane Perfect Matchings into a Point Set PDF
Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid 119-142

ISSN: 1365-8050