ABSTRACT

Methods for computing graph polynomials have received considerable attention in the literature. This chapter discusses a logic-based approach which guarantees efficient computation of graph polynomials on special families of graphs. It introduces a logical framework for defining graphs polynomials and show that graph polynomials which belong to this framework can be computed efficiently in two settings: On families of graphs of bounded width, such graph polynomials can be computed in polynomial time; On sequences of graphs which are constructed in an iterative manner, such graph polynomials satisfy simple recurrence relations. The chapter presents the logic-based framework which generalizes the methods discussed above from specific, well-studied examples to an infinite class of graph polynomials covering most of the graph polynomials studied in the literature. It assumes that the reader is familiar with the basic notions of first-order logic: formula, sentence, logical implication, etc.