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

DOI10.1016/j.dam.2024.07.014zbMATH Open1547.05206MaRDI QIDQ6611075

Asahi Takaoka

Publication date: 26 September 2024

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Max point-tolerance graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Representing graphs via pattern avoiding words
• On orthogonal ray graphs
• Words and graphs
• Semi-transitive orientations and word-representable graphs
• An optimal greedy heuristic to color interval graphs
• Stack sortable permutations
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• A short proof that `proper = unit'
• Efficient graph representations
• On graphs representable by pattern-avoiding words
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• A vertex ordering characterization of simple-triangle graphs
• Algorithmic graph theory and perfect graphs
• List homomorphisms and circular arc graphs
• Maximum induced matching algorithms via vertex ordering characterizations
• Describing hereditary properties by forbidden circular orderings
• On the 12-representability of induced subgraphs of a grid graph
• Recognizing simple-triangle graphs by restricted 2-chain subgraph cover
• A recognition algorithm for simple-triangle graphs
• On grounded \(\llcorner\)-graphs and their relatives
• A comprehensive introduction to the theory of word-representable graphs
• A recognition algorithm for adjusted interval digraphs
• On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
• Ordering without Forbidden Patterns
• Graph Classes: A Survey
• A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
• On 132-representable Graphs
• Existence of u -Representation of Graphs
• Min-Orderable Digraphs
• (c-)AND: A new graph model
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• On representable graphs
• Graph Classes and Forbidden Patterns on Three Vertices
• Recognition and drawing of stick graphs
• Characterizing star-PCGs
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Recognizing interval bigraphs by forbidden patterns
• Comparability digraphs: an analogue of comparability graphs
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices

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