2010/12/17 by Adam Bohn, Bohn, Adam · 1 citation
Engineering · Computer Science · #graph theory and CDMA systems #Graph Labeling and Dimension Problems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1012.3847
We introduce a class of pairs of graphs consisting of two cliques joined by an arbitrary number of edges. The members of a pair have the property that the clique-bridging edge-set of one graph is the complement of that of the other. We prove a precise relation between the chromatic polynomials of the graphs in such a pair, showing that they have the same splitting field, and that the number of acyclic orientations of each graph is determined by the number of proper vertex-colourings of the other.