Colorings and interpretations: a connection between graphs and grammar forms

DOI10.1016/0166-218X(81)90037-8zbMath0466.05034OpenAlexW1980790276MaRDI QIDQ1155066

Derick Wood, Arto Salomaa, Hermann Maurer

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0166-218x(81)90037-8

zbMATH Keywords

grammar formscolorable families of graphshierarchies of graph- families

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Coloring of graphs and hypergraphs (05C15)

Related Items

Good and semi-strong colorings of oriented planar graphs, On the complexity of H-coloring, Colorings and girth of oriented planar graphs, On minimal graphs, Homomorphic preimages of geometric paths, Completeness of context-free grammar forms, Color-families are dense, Polynomial graph-colorings, On the General Coloring Problem, Polynomial graph-colorings, Hereditarily hard \(H\)-colouring problems, On finite grammar forms, Finitary and infinitary interpretations of languages, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, Symmetric graphs and interpretations, Homomorphisms of 3-chromatic graphs, Subdivision of the hierarchy of H-colorable graph classes by circulant graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Grammar and L forms: an introduction
• Context-free grammar forms with strict interpretations
• Decidability and density in two-symbol grammar forms
• Parallel concepts in graph theory
• Graph Theory and Probability. II
• Dense Hierarchies of Grammatical Families
• MSW spaces
• On finite grammar forms