Connection Matrices for MSOL-Definable Structural Invariants

DOI10.1007/978-3-540-92701-3_4MaRDI QIDQ3601800zbMATH OpenOpenAlexFDO

Authors Johann A. Makowsky

Publication date 12 February 2009

Published in Logic and Its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92701-3_4

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph polynomials (05C31) Logic in computer science (03B70)

Recommendations

• Connection matrices and the definability of graph parameters
• Connection matrices and the definability of graph parameters
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 952951
• Parameterized and Exact Computation
• scientific article; zbMATH DE number 5057511
• The Connection Matrix Theory for Morse Decompositions
• Basic Constructive Connectives, Determinism and Matrix-Based Semantics
• Morse decompositions and connection matrices
• A characterization of invariant connections

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 994578 (Why is no real title available?)
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 1057876 (Why is no real title available?)
• scientific article; zbMATH DE number 3298599 (Why is no real title available?)
• Algorithmic uses of the Feferman-Vaught theorem
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Connection matrices
• Edge coloring models and reflection positivity
• Efficient approximation of convex recolorings
• Evaluations of Graph Polynomials
• Graph-Theoretic Concepts in Computer Science
• Hard Enumeration Problems in Geometry and Combinatorics
• On Counting Generalized Colorings
• On the Harmonious Coloring of Graphs
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Parity, Eulerian subgraphs and the Tutte polynomial
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Some new evaluations of the Tutte polynomial
• The complexity of harmonious colouring for trees
• The interlace polynomial of a graph
• Upper bounds to the clique width of graphs

Cited in

(4)

• Finiteness conditions for graph algebras over tropical semirings
• Connection matrices and the definability of graph parameters
• Connection matrices and the definability of graph parameters
• Connection matrices

This page was built for publication: Connection Matrices for MSOL-Definable Structural Invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3601800)