Thickness and colorability of geometric graphs (Q679741): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/j.comgeo.2016.03.003 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2302259827 / rank | |||
Normal rank | |||
Revision as of 19:57, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Thickness and colorability of geometric graphs |
scientific article |
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
