In this work, we present an extension to the recently developed Integer and Categorical Particle Swarm Optimization (ICPSO), which we refer to as Markovian ICPSO (MICPSO). MICPSO uses a Markov network to represent a particle's position, thus allowing each particle to incorporate information about dependencies between solution variables. In this work, we compare MICPSO to ICPSO, Integer PSO (IPSO), an Estimation of Distribution Algorithm called Markovianity-Based Optimization Algorithm (MOA), and a hillclimber on a set of benchmark vertex coloring problems. We find that MICPSO significantly outperforms all alternatives on all problems tested.