Maximal nontraceable graphs with toughness less than one.
Bullock, Frank; Frick, Marietjie; Singleton, Joy; van Aardt, Susan; Mynhardt, Kieka (C.M.) — 2008
The Electronic Journal of Combinatorics [electronic only]
Maximal nontraceable graphs with toughness less than one.
Detour chromatic numbers
The nth detour chromatic number, χₙ(G) of a graph G is the minimum number of colours required to colour the vertices of G such that no path with more than n vertices is monocoloured. The number of vertices in a longest path of G is denoted by τ( G). We conjecture that χₙ(G) ≤ ⎡(τ(G))/n⎤ for every graph G and every n ≥ 1 and we prove results that support the conjecture. We also present some sufficient conditions for a graph to have nth chromatic number at most 2.
Hamiltonicity of -traceable graphs.
Page 1