机构:
Technion Israel Inst Technol, Fac Comp Sci, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Comp Sci, IL-32000 Haifa, Israel
Kotek, Tomer
[1
]
Makowsky, Johann A.
论文数: 0引用数: 0
h-index: 0
机构:
Technion Israel Inst Technol, Fac Comp Sci, IL-32000 Haifa, IsraelTechnion Israel Inst Technol, Fac Comp Sci, IL-32000 Haifa, Israel
Makowsky, Johann A.
[1
]
论文数: 引用数:
h-index:
机构:
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.
机构:
Univ Politecn Cataluna, ALBCOM Res Grp, Dept Llenguatges & Sistemes Informat, Barcelona 08034, SpainUniv Politecn Cataluna, ALBCOM Res Grp, Dept Llenguatges & Sistemes Informat, Barcelona 08034, Spain
Diaz, Josep
Serna, Maria
论文数: 0引用数: 0
h-index: 0
机构:
Univ Politecn Cataluna, ALBCOM Res Grp, Dept Llenguatges & Sistemes Informat, Barcelona 08034, SpainUniv Politecn Cataluna, ALBCOM Res Grp, Dept Llenguatges & Sistemes Informat, Barcelona 08034, Spain
Serna, Maria
Thilikos, Dimitrios M.
论文数: 0引用数: 0
h-index: 0
机构:
Natl & Kapodistrian Univ Athens, Dept Math, GR-15784 Athens, GreeceUniv Politecn Cataluna, ALBCOM Res Grp, Dept Llenguatges & Sistemes Informat, Barcelona 08034, Spain