Linear forest
http://dbpedia.org/resource/Linear_forest
In graph theory, a branch of mathematics, a linear forest is a kind of forest formed from the disjoint union of path graphs. It is an undirected graph with no cycles in which every vertex has degree at most two. Linear forests are the same thing as claw-free forests. They are the graphs whose Colin de Verdière graph invariant is at most 1. The linear arboricity of a graph is the minimum number of linear forests into which the graph can be partitioned. For a graph of maximum degree , the linear arboricity is always at least , and it is conjectured that it is always at most .
rdf:langString
Линейный лес — это вид леса, образованного из дизъюнктного объединения путей. Это ориентированный граф, не имеющий циклов, в котором каждая вершина имеет степень, не превосходящую трёх. Линейные леса — это то же самое, что и леса без клешенй. Это также графы, инвариант Колен де Вердьера которых не превосходит 1. Линейная древесность графа — это минимальное число линейных лесов, на которые граф может быть разложен. Для графа максимальной степени линейная древесность всегда не менее , и есть гипотеза, что она всегда не превосходит .
rdf:langString
rdf:langString
Linear forest
rdf:langString
Линейный лес
xsd:integer
36344169
xsd:integer
1062224590
rdf:langString
In graph theory, a branch of mathematics, a linear forest is a kind of forest formed from the disjoint union of path graphs. It is an undirected graph with no cycles in which every vertex has degree at most two. Linear forests are the same thing as claw-free forests. They are the graphs whose Colin de Verdière graph invariant is at most 1. The linear arboricity of a graph is the minimum number of linear forests into which the graph can be partitioned. For a graph of maximum degree , the linear arboricity is always at least , and it is conjectured that it is always at most . A linear coloring of a graph is a proper graph coloring in which the induced subgraph formed by each two colors is a linear forest. The linear chromatic number of a graph is the smallest number of colors used by any linear coloring. The linear chromatic number is at most proportional to , and there exist graphs for which it is at least proportional to this quantity.
rdf:langString
Линейный лес — это вид леса, образованного из дизъюнктного объединения путей. Это ориентированный граф, не имеющий циклов, в котором каждая вершина имеет степень, не превосходящую трёх. Линейные леса — это то же самое, что и леса без клешенй. Это также графы, инвариант Колен де Вердьера которых не превосходит 1. Линейная древесность графа — это минимальное число линейных лесов, на которые граф может быть разложен. Для графа максимальной степени линейная древесность всегда не менее , и есть гипотеза, что она всегда не превосходит . Линейная раскраска графа — это собственная раскраска графов, в которой порождённый подграф, образованный любыми двумя цветами, образует линейный лес. Линейное хроматическое число графа — это наименьшее число цветов, используемых для любой линейной раскраски. Линейное хроматическое число как максимум пропорционально (где — максимальная степень графа) и есть графы, для которых оно по меньшей мере пропорционально этой величине.
xsd:nonNegativeInteger
2479