
doi: 10.7151/dmgt.1150
Let \(\tau(G)\) denote the number of vertices in a longest path of a graph \(G\). The \(n\)th detour number \(\chi_n(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. It is shown that the path partition conjecture, formulated by P. Mihók (see \textit{M. Borowiecki}, et al. [Discuss. Math., Graph Theory 17, 5-50 (1997; Zbl 0902.05026)]), is strongly related to the conjecture that \(\chi_n(G)\leq \lceil \frac{\tau(G)}n \rceil\) for every graph \(G\) and every \(n\geq 1\). Some results determining \(\chi_n(G)\) for particular classes of graphs are presented. Sufficient conditions for graphs with \(n\)th chromatic number at most \(2\) are provided as well.
Coloring of graphs and hypergraphs, detour, generalized colouring, path partition conjecture, nearly bipartite, Paths and cycles
Coloring of graphs and hypergraphs, detour, generalized colouring, path partition conjecture, nearly bipartite, Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
