Thickness and colorability of geometric graphs (Q679741)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Thickness and colorability of geometric graphs |
scientific article; zbMATH DE number 6827953
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Thickness and colorability of geometric graphs |
scientific article; zbMATH DE number 6827953 |
Statements
Thickness and colorability of geometric graphs (English)
0 references
19 January 2018
0 references
The authors consider the thickness and geometric thickness of graphs. They give an example of a graph with thickness equal to 2 and geometric thickness equal to 3. They prove that the problem of recognizing geometric thickness is NP-hard even for graphs with geometric thickness equal to 2. Moreover, they give the proof of NP-hardness of \((4t-1)\)-coloring graphs with geometric thickness \(t\). The paper improves known results in this topic.
0 references
complete graph
0 references
geometric thickness
0 references
coloring
0 references
