On the 12-representability of induced subgraphs of a grid graph

DOI10.7151/DMGT.2263zbMath1489.05106arXiv1911.00408OpenAlexW2990122721MaRDI QIDQ2118234

Joanna N. Chen, Sergey Kitaev

Publication date: 22 March 2022

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.00408

zbMATH Keywords

grid graphgraph representationforbidden subgraphsquare grid graph12-representable graphline grid graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Representing graphs via pattern avoiding words
• Words and graphs
• Online coloring co-interval graphs
• A comprehensive introduction to the theory of word-representable graphs
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• Existence of u -Representation of Graphs

This page was built for publication: On the 12-representability of induced subgraphs of a grid graph