An application of graph coloring to printed circuit testing

A proposed method for testing printed circuit boards for the existence of possible (undesired) short circuits transforms the test minimization problem into one of finding minimum vertex colorings of certain special graphs, called line-of-sight graphs. Under certain assumptions on the possible types of short circuits, we analyze the structure of such graphs and show that a well-known and efficient algorithm can be used to color them with a small number of colors. In particular, we show that no more than 5, 8, or 12 colors (depending on the particular assumptions) will ever be required for such a graph, independent of the number of vertices. Thus, in such cases, the potential advantage of the proposed method over exhaustive testing could be considerable.