On Counting Generalized Colorings

被引:0
|
作者
Kotek, Tomer [1 ]
Makowsky, Johann A. [1 ]
Zilber, Boris [2 ]
机构
[1] Technion Israel Inst Technol, Fac Comp Sci, IL-32000 Haifa, Israel
[2] Univ Oxford, Inst Math, Oxford OX1 3LB, England
来源
MODEL THEORETIC METHODS IN FINITE COMBINATORICS | 2011年 / 558卷
基金
以色列科学基金会;
关键词
COMPLEXITY; GRAPHS; ZOOLOGY; NUMBER; ZOO;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The notion of graph polynomials definable in Monadic Second Order Logic, MSOL, was introduced by B. Courcelle, J.A. Makowsky and U. Rotics in 2001. It was shown later that the Tutte polynomial and generalizations of it, as well as the matching polynomial, the cover polynomial and the various interlace polynomials fall into this category. In this article we present a uniform model theoretic framework for studying graph polynomials. In particular we study an infinite class of graph polynomials based on counting functions of generalized colorings definable in full second order logic SOL.
引用
收藏
页码:207 / +
页数:4
相关论文
共 50 条
  • [41] Counting H-colorings of partial k-trees
    Díaz, J
    Serna, M
    Thilikos, DM
    THEORETICAL COMPUTER SCIENCE, 2002, 281 (1-2) : 291 - 309
  • [42] Efficient algorithms for counting parameterized list H-colorings
    Diaz, Josep
    Serna, Maria
    Thilikos, Dimitrios M.
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (05) : 919 - 937
  • [43] ON THE EXISTENCE OF GENERALIZED GOOD AND EQUITABLE EDGE COLORINGS
    DEWERRA, D
    JOURNAL OF GRAPH THEORY, 1981, 5 (03) : 247 - 258
  • [44] GENERALIZED FRACTIONAL AND CIRCULAR TOTAL COLORINGS OF GRAPHS
    Kemnitz, Arnfried
    Marangio, Massimiliano
    Mihok, Peter
    Oravcova, Janka
    Sotak, Roman
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2015, 35 (03) : 517 - 532
  • [45] GENERALIZED FRACTIONAL TOTAL COLORINGS OF COMPLETE GRAPHS
    Karafova, Gabriela
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (04) : 665 - 676
  • [46] APPROXIMATELY COUNTING H-COLORINGS IS #BIS-HARD
    Galanis, Andreas
    Goldberg, Leslie Ann
    Jerrum, Mark
    SIAM JOURNAL ON COMPUTING, 2016, 45 (03) : 680 - 711
  • [47] Counting the number of non-equivalent vertex colorings of a graph
    Hertz, Alain
    Melot, Hadrien
    DISCRETE APPLIED MATHEMATICS, 2016, 203 : 62 - 71
  • [48] Counting of generalized polarizabilities
    Lebed, RF
    PHYSICAL REVIEW D, 2001, 64 (09):
  • [49] An algebraic approach for counting DP-3-colorings of sparse graphs
    Dahlberg, Samantha L.
    Kaul, Hemanshu
    Mudrock, Jeffrey A.
    EUROPEAN JOURNAL OF COMBINATORICS, 2024, 118
  • [50] Improved exact algorithms for counting 3-and 4-colorings
    Fomin, Fedor V.
    Gaspers, Serge
    Saurabh, Saket
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2007, 4598 : 65 - +