Non-repetitive 3-coloring of subdivided graphs (Q1028809)
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: Non-repetitive 3-coloring of subdivided graphs |
scientific article; zbMATH DE number 5576415
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Non-repetitive 3-coloring of subdivided graphs |
scientific article; zbMATH DE number 5576415 |
Statements
Non-repetitive 3-coloring of subdivided graphs (English)
0 references
8 July 2009
0 references
Summary: We show that every graph can be subdivided in a way that the resulting graph can be colored without repetitions on paths using only 3 colors. This extends the result of Thue asserting the existence of arbitrarily long nonrepetitive strings over a 3-letter alphabet.
0 references
0.895646333694458
0 references
0.8614361882209778
0 references
0.8428147435188293
0 references
0.8327459096908569
0 references
0.8226764798164368
0 references
