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 条
  • [21] Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds
    Couturier, Jean-Francois
    Golovach, Petr A.
    Kratsch, Dieter
    Liedloff, Mathieu
    Pyatkin, Artem
    THEORY OF COMPUTING SYSTEMS, 2013, 52 (04) : 645 - 667
  • [22] ON MULTISET COLORINGS OF GENERALIZED CORONA GRAPHS
    Feng, Yun
    Lin, Wensong
    MATHEMATICA BOHEMICA, 2016, 141 (04): : 431 - 455
  • [23] TAIT COLORINGS ON GENERALIZED PETERSEN GRAPHS
    CASTAGNA, F
    PRINS, GCE
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1970, 17 (04): : 639 - &
  • [24] Graph clustering via generalized colorings
    London, Andras
    Martin, Ryan R.
    Pluhar, Andras
    THEORETICAL COMPUTER SCIENCE, 2022, 918 : 94 - 104
  • [25] BACKBONE COLORINGS AND GENERALIZED MYCIELSKI GRAPHS
    Miskuf, Jozef
    Skrekovski, Riste
    Tancer, Martin
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (02) : 1063 - 1070
  • [26] Correlation decay and deterministic FPTAS for counting colorings of a graph
    Gamarnik, David
    Katz, Dmitriy
    JOURNAL OF DISCRETE ALGORITHMS, 2012, 12 : 29 - 47
  • [27] Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds
    Jean-Francois Couturier
    Petr A. Golovach
    Dieter Kratsch
    Mathieu Liedloff
    Artem Pyatkin
    Theory of Computing Systems, 2013, 52 : 645 - 667
  • [28] Exact algorithms for counting 3-colorings of graphs
    Zhu, Enqiang
    Wu, Pu
    Shao, Zehui
    Discrete Applied Mathematics, 2022, 322 : 74 - 93
  • [29] On the chromatic polynomial and counting DP-colorings of graphs
    Kaul, Hemanshu
    Mudrock, Jeffrey A.
    ADVANCES IN APPLIED MATHEMATICS, 2021, 123
  • [30] Exact algorithms for counting 3-colorings of graphs
    Zhu, Enqiang
    Wu, Pu
    Shao, Zehui
    DISCRETE APPLIED MATHEMATICS, 2022, 322 : 74 - 93