On Hamiltonian colorings of graphs (Q1772412)
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: On Hamiltonian colorings of graphs |
scientific article; zbMATH DE number 2157727
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On Hamiltonian colorings of graphs |
scientific article; zbMATH DE number 2157727 |
Statements
On Hamiltonian colorings of graphs (English)
0 references
18 April 2005
0 references
The authors give a lower bound for the circumference of a graph in terms of the number of vertices that receive colors between two specified colors in a Hamiltonian coloring of the graph. As a consequence, if there exists a Hamiltonian coloring of a connected graph \(G\) of order \(n\) such that at least \((n+2)/2\) vertices of \(G\) are colored with one of two consecutive colors, then the circumference of \(G\) is at least \(n-1\).
0 references
Hamiltonian colorings
0 references
Hamiltonian-connected graphs
0 references
circumference
0 references
