The monadic second order logic of graphs. VI: On several representations of graphs by relational structures

DOI10.1016/0166-218X(94)90019-1zbMath0809.03005MaRDI QIDQ1336623

Bruno Courcelle

Publication date: 3 November 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

minorHamiltonian cycleplanaritytreesexpressive powerorientationscoloringsmonadic second order logiclogic definabilityquantifications over edges and sets of edgesrepresentation of graphs by logical structures

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Second- and higher-order model theory (03C85)

Related Items

Trees, grids, and MSO decidability: from graphs to matroids, The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., Good and semi-strong colorings of oriented planar graphs, Oriented incidence colourings of digraphs, Plurigraph coloring and scheduling problems, On fractional version of oriented coloring, Oriented vertex and arc colorings of outerplanar graphs, On oriented relative clique number, The acircuitic directed star arboricity of subcubic graphs is at most four, On spectra of sentences of monadic second order logic with counting, The monadic second-order logic of graphs. X: Linear orderings, Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, Recognizability equals definability for partial k-paths, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, MSOL partitioning problems on graphs of bounded treewidth and clique-width, On the minimum cycle cover problem on graphs with bounded co-degeneracy, On deeply critical oriented cliques, Complete oriented colourings and the oriented achromatic number, Injectively \(k\)-colored rooted forests, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, The smallest 5-chromatic tournament, Oriented vertex and arc colorings of partial 2-trees, Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs, Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\), The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree, Classes of intersection digraphs with good algorithmic properties, On the oriented achromatic number of graphs, A homomorphic polynomial for oriented graphs, The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs, Pushable chromatic number of graphs with degree constraints, Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs, Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs, Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs, Efficient computation of the oriented chromatic number of recursively defined digraphs, Characterization and complexity of uniformly nonprimitive labeled 2-structures, The definition in monadic second-order logic of modular decompositions of ordered graphs, A study on oriented relative clique number, Oriented coloring on recursively defined digraphs, Unnamed Item, Logical aspects of Cayley-graphs: the group case, Oriented colorings of partial 2-trees, Recognizability, hypergraph operations, and logical types, On the oriented chromatic number of graphs with given excess, Unnamed Item, Unnamed Item, Outerplanar and Planar Oriented Cliques, Computing with graph rewriting systems with priorities, Unnamed Item, Oriented cliques and colorings of graphs with low maximum degree, An oriented coloring of planar graphs with girth at least five, The monadic second-order logic of graphs. XII: Planar graphs and planar maps, On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets, Chromatic polynomials of oriented graphs, The closure of monadic NP, The recognizability of sets of graphs is a robust property, The monadic second-order logic of graphs. VIII: Orientations

Cites Work

• The structure of the models of decidable monadic theories of graphs
• Forbidden minors characterization of partial 3-trees
• A comparison of boundary graph grammars and context-free hypergraph grammars
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Some combinatorial aspects of time-stamp systems
• Advances in graph theory
• Hypergraph languages of bounded degree
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Beweis einer Abschwächung der Hadwiger-Vermutung
• Graph minors. IV: Tree-width and well-quasi-ordering
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Reachability is harder for directed than for undirected finite graphs
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Languages that Capture Complexity Classes
• Graph expressions and graph rewritings
• Recursive Graphs, Recursive Labelings and Shortest Paths
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decomposition of Finite Graphs Into Forests
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item