This book constitutes the refereed proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science, DMTCS 2003, held in Dijon, France in July 2003. The 18 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 35 submissions. A broad variety of topics in discrete mathematics and the theory of computing is addressed including information theory, coding, algorithms, complexity, automata, computational mathematics, combinatorial computations, graph computations, algorithmic geometry, relational methods, game-theoretic methods, combinatorial optimization, finite state systems, etc.