Hard-to-color graphs for connected sequential colorings (Q1329800)
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: Hard-to-color graphs for connected sequential colorings |
scientific article; zbMATH DE number 612426
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hard-to-color graphs for connected sequential colorings |
scientific article; zbMATH DE number 612426 |
Statements
Hard-to-color graphs for connected sequential colorings (English)
0 references
26 January 1995
0 references
A graph \(G\) is said to be hard-to-colour if any connected colouring produces a nonoptimal colouring, and partially hard-to-colour if any such colouring starting in a specified vertex is nonoptimal. The authors show that the linked pair of twin kites with 18 vertices is the smallest cubic hard-to-colour graph and they conjecture that this graph is the smallest graph hard-to-colour from any starting point.
0 references
connected colouring
0 references
hard-to-colour graph
0 references
0.90786844
0 references
0 references
0.90570205
0 references
0 references
0.89615154
0 references
0.8946973
0 references
