  Many variations of the classical graph coloring model have been intensively
studied due to their multiple applications; scheduling problems and aircraft
assignments, for instance, motivate the robust coloring problem. This model
gets to capture natural constraints of those optimization problems by combining
the information provided by two colorings: a vertex coloring of a graph and the
induced edge coloring on a subgraph of its complement; the goal is to minimize,
among all proper colorings of the graph for a fixed number of colors, the
number of edges in the subgraph with the endpoints of the same color. The study
of the robust coloring model has been focused on the search for heuristics due
to its NP-hard character when using at least three colors, but little progress
has been made in other directions. We present a new approach on the problem
obtaining the first collection of non-heuristic results for general graphs;
among them, we prove that robust coloring is the model that better approaches
the equitable partition of the vertex set, even when the graph does not admit a
so-called \emph{equitable coloring}. We also show the NP-completeness of its
decision problem for the unsolved case of two colors, obtain bounds on the
associated robust coloring parameter, and solve a conjecture on paths that
illustrates the complexity of studying this coloring model.

Discrete Mathematics;Combinatorics