Graph thinness: a lower bound and complexity
The idea of $k$-thin graphs has emanated from applications to frequency assignment problems. The graphs considered by the author here are only undirected simple graphs. The goal of this article is to prove that graph thinness is NP complete and to show that there exist graphs with thinness $n -o(n)$ where $n$ refers to the number of vertices of $G$. The author achieves his goal by splitting the proof into several lemmas and also raises an open problem in the end by asking whether there exists a graph on $n$ vertices with thinness more than half of $n$.
- 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)
