Linear k-arboricity of a graph
Перейти к навигации
Перейти к поиску
Linear [math]\displaystyle{ k }[/math]-arboricity of a graph --- линейная древесность графа. The linear [math]\displaystyle{ k }[/math]-arboricity of a graph [math]\displaystyle{ G }[/math], denoted by [math]\displaystyle{ la_{k}(G) }[/math], is the least integer [math]\displaystyle{ m }[/math] such that [math]\displaystyle{ G }[/math] can be edge-partitioned into [math]\displaystyle{ m }[/math] linear [math]\displaystyle{ k }[/math]-forests. Clearly, [math]\displaystyle{ la_{1}(G) }[/math] is the edge chromatic number, or chromatic index [math]\displaystyle{ \chi'(G) }[/math] of [math]\displaystyle{ G }[/math].
The linear [math]\displaystyle{ k }[/math]-arboricity of a graph was first introduced by M. Habib and P. P\'{e}roche (1982).