Abstract
It is well known that the number of proper k-colorings of a graph is a polynomial in k. We investigate in this talk under what conditions a numeric graph invariant which is parametrized with parameters k 1, ..., k m is a polynomial in these parameters. We give a sufficient conditions for this to happen which is general enough to encompass all the graph polynomials which are definable in Second Order Logic. This not only covers the various generalizations of the Tutte polynomials, Interlace polynomials, Matching polynomials, but allows us to identify new graph polynomials related to combinatorial problems discussed in the literature.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Ding, G., Oporowski, B., Vertigan, D.: Partitioning into graphs with only small components. Journal of Combinatorial Theory, Series B 87, 231–243 (2003)
Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)
Bollobás, B.: Modern Graph Theory. Springer, Heidelberg (1999)
Courcelle, B., Godlin, B., Makowsky, J.A.: Towards a theory of graph polynomials, I: Second order definable polynomials (in preparation, 2007)
Courcelle, B.: A multivariate interlace polynomial (December 2006) (preprint)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics. Springer, Heidelberg (1996)
Dong, F.M., Koh, K.M., Teo, K.L.: Chromatic Polynomials and Chromaticity of Graphs. World Scientific, Singapore (2005)
Edwards, K.: The harmonious chromatic number and the achromatic number. In: Bailey, R.A. (ed.) Survey in Combinatorics. London Math. Soc. Lecture Note Ser, vol. 241, pp. 13–47. Cambridge Univ. Press, Cambridge (1997)
Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Perspectives in Mathematical Logic. Springer, Heidelberg (1995)
Ebbinghaus, H.D., Flum, J., Thomas, W.: Mathematical Logic, 2nd edn. Undergraduate Texts in Mathematics. Springer, Heidelberg (1994)
Edwards, K., McDiarmid, C.: The complexity of harmonious colouring for trees. Discrete Appl. Math. 57(2-3), 133–144 (1995)
Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall, Boca Raton (1993)
Harary, F., Hedetniemi, S., Rins, G.: An interpolation theorem for graphical homomorphisms. Portugal. Math. 26, 453–462 (1967)
Hopcroft, J.E., Krishnamoorthy, M.S.: On the harmonious coloring of graphs. SIAM J. Algebraic Discrete Methods 4, 306–311 (1983)
Hughes, F., MacGillivray, G.: The achromatic number of graphs: a survey and some new results. Bull. Inst. Combin. Appl. 19, 27–56 (1997)
Libkin, L.: Elements of Finite Model Theory. Springer, Heidelberg (2004)
Linial, N., Matoušek, J., Sheffet, O., Tardos, G.: Graph coloring with no large monochromatic components (2007) arXiv:math/0703362v1
Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Annals of Pure and Applied Logic 126(1-3), 159–213 (2004)
Makowsky, J.A.: From a zoo to a zoology: Descriptive complexity for graph polynomials. In: Beckmann, A., Berger, U., Löwe, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol. 3988, pp. 330–341. Springer, Heidelberg (2006)
Makowsky, J.A., Zilber, B.: Polynomial invariants of graphs and totally categorical theories. MODNET Preprint No. 21 (2006), http://www.logique.jussieu.fr/modnet/Publications/Preprint%20server
Noble, S.D., Welsh, D.J.A.: A weighted graph polynomial from chromatic invariants of knots. Ann. Inst. Fourier, Grenoble 49, 1057–1087 (1999)
Sokal, A.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Survey in Combinatorics, 2005. London Mathematical Society Lecture Notes, vol. 327, pp. 173–226 (2005)
Toda, S., Watanabe, O.: Polynomial time 1-Turing reductions from #PH to #P. Theor. Comp. Sc. 100, 205–221 (1992)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kotek, T., Makowsky, J.A., Zilber, B. (2008). On Counting Generalized Colorings. In: Kaminski, M., Martini, S. (eds) Computer Science Logic. CSL 2008. Lecture Notes in Computer Science, vol 5213. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87531-4_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-87531-4_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87530-7
Online ISBN: 978-3-540-87531-4
eBook Packages: Computer ScienceComputer Science (R0)