We define specific multiplicities on the braid arrangement by using edge-bicolored graphs. To consider their freeness, we introduce the notion of bicolor-eliminable graphs as a generalization of Stanleys classification theory of free graphic arrangements by chordal graphs. This generalization gives us a complete classification of the free multiplicities defined above. As an application, we prove one direction of a conjecture of Athanasiadis on the characterization of the freeness of the deformation of the braid arrangement in terms of directed graphs.