Combinatorial properties of boundary NLC graph languages

DOI10.1016/0166-218X(87)90054-0zbMath0619.68063OpenAlexW2080485683WikidataQ54309830 ScholiaQ54309830MaRDI QIDQ1089808

Grzegorz Rozenberg, Ermo Welzl

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0166-218x(87)90054-0

zbMATH Keywords

chromatic numberclique numbergraph grammarsindex of a graphnode label controlled grammarsadjacency structurebehaviour of graph invariantsBNLC languagesnode labeled undirected graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Structural characterization of families of graphs (05C75)

Related Items

The complexity of connectivity problems on context-free graph languages, The equivalence of boundary and confluent graph grammars on graph languages of bounded degree, Logical description of context-free graph languages, Boundary graph grammars with dynamic edge relabeling, A comparison of boundary graph grammars and context-free hypergraph grammars, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, Algorithms for graph problems on BNLC structured garphs, Linear graph grammars: Power and complexity, On hyperedge replacement and BNLC graph grammars, Nonterminal separation in graph grammars, Separating \(k\)-separated eNCE graph languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restrictions on NLC graph grammars
• Graph theoretic closure properties of the family of boundary NLC graph languages
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• Decision problems for node label controlled graph grammars
• Parallel concepts in graph theory
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Sur le coloriage des graphs