Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words

DOI10.1016/J.DAM.2024.07.014MaRDI QIDQ6611075zbMATH OpenFDO

Authors Asahi Takaoka

Publication date 26 September 2024

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

Full work available at URL https://doi.org/10.1016/J.DAM.2024.07.014

zbMATH Keywords

pattern avoidanceword-representable graphssimple-triangle graphsvertex orderings with forbidden patterns12-representable graphsmax point-tolerance graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Combinatorics on words (68R15)

Recommendations

• Representing graphs via pattern avoiding words
• On 132-representable graphs
• On graphs representable by pattern-avoiding words

Cites work

• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• A comprehensive introduction to the theory of word-representable graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• A recognition algorithm for adjusted interval digraphs
• A recognition algorithm for simple-triangle graphs
• A short proof that `proper = unit'
• A vertex ordering characterization of simple-triangle graphs
• Algorithmic graph theory and perfect graphs
• An optimal greedy heuristic to color interval graphs
• Characterisations of intersection graphs by vertex orderings
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Comparability digraphs: an analogue of comparability graphs
• Describing hereditary properties by forbidden circular orderings
• Efficient graph representations
• Existence of u-representation of graphs
• Graph Classes: A Survey
• Graph classes and forbidden patterns on three vertices
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• List homomorphisms and circular arc graphs
• Max point-tolerance graphs
• Maximum induced matching algorithms via vertex ordering characterizations
• Min-orderable digraphs
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• On 132-representable graphs
• On graphs representable by pattern-avoiding words
• On grounded -graphs and their relatives
• On orthogonal ray graphs
• On representable graphs
• On the 12-representability of induced subgraphs of a grid graph
• On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
• Ordering without forbidden patterns
• Recognizing interval bigraphs by forbidden patterns
• Representing graphs via pattern avoiding words
• Semi-transitive orientations and word-representable graphs
• Stack sortable permutations
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• Words and graphs
• p-box: a new graph model

Cited in

(1)

• Computing shortest 12-representants of labeled graphs

This page was built for publication: Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words

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