Graph thinness: a lower bound and complexity

DOI10.2140/PJM.2025.339.333MaRDI QIDQ6925839zbMATH OpenFDO

Authors Ya. N. Shitov

Publication date 25 September 2025

Published in Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2140/PJM.2025.339.333

zbMATH Keywords

NP-completenessinterval graph\(k\)-thin graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites work

• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Efficient algorithms for interval graphs and circular-arc graphs
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• On the thinness and proper thinness of a graph
• Precedence thinness in graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The stable set problem and the thinness of a graph
• Thinness of product graphs

This page was built for publication: Graph thinness: a lower bound and complexity

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