Word-representability of graphs with respect to split recomposition

DOI10.1016/J.DAM.2024.06.022MaRDI QIDQ6611031zbMATH OpenFDO

Authors Tithi Dwary, K. V. Krishna

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.06.022

zbMATH Keywords

\textit{prn}-irreducible graphcomparability graphsprnrepresentation numbersplit recompositionword-representable graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Representing split graphs by words
• Word-representability of split graphs generated by morphisms
• Word-representability of split graphs
• Word-Representable Graphs: a Survey
• Parikh word representability of bipartite permutation graphs

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A Combinatorial Decomposition Theory
• Algorithmic graph theory and perfect graphs
• Alternation graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Completely separable graphs
• Decomposition of Directed Graphs
• Distance labeling scheme and split decomposition
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Enumerations, forbidden subgraph characterizations, and the split-decomposition
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3887730 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 3318593 (Why is no real title available?)
• scientific article; zbMATH DE number 3390792 (Why is no real title available?)
• Maximal dimensional partially ordered sets. I: Hiraguchi's theorem
• On representable graphs
• On sources in comparability graphs, with applications
• On the extension of bipartite to parity graphs
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Partially ordered sets.
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• Reducing prime graphs and recognizing circle graphs
• Solving some NP-complete problems using split decomposition
• Sources in posets and comparability graphs
• The 3-Irreducible Partially Ordered Sets
• The Complexity of the Partial Order Dimension Problem
• The graph sandwich problem for 1-join composition is NP-complete
• Transforming trees by successive local complementations
• Transitiv orientierbare Graphen
• Treelike comparability graphs
• Word problem of the Perkins semigroup via directed acyclic graphs.
• Words and graphs

Cited in

(1)

• Characterization of double-arborescences and their minimum length word-representants

This page was built for publication: Word-representability of graphs with respect to split recomposition

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