Star coloring
http://dbpedia.org/resource/Star_coloring
In the mathematical field of graph theory, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by .The star chromatic number of G is the fewest colors needed to star color G.
rdf:langString
Звёздная раскраска в теории графов — (правильная) раскраска вершин, в которой любой путь из четырёх вершин использует как минимум три различных цвета. Эквивалентное определение — это такая раскраска, при которой любые компоненты связности порождённых подграфов, образованных вершинами любых двух цветов, являются звёздами. Звёздная раскраска была предложена Грюнбаумом. Звёздное хроматическое число графа — это минимальное число цветов, необходимых для получения звёздной раскраски .
rdf:langString
rdf:langString
Star coloring
rdf:langString
Звёздная раскраска
xsd:integer
20933302
xsd:integer
1108315638
rdf:langString
In the mathematical field of graph theory, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by .The star chromatic number of G is the fewest colors needed to star color G. One generalization of star coloring is the closely related concept of acyclic coloring, where it is required that every cycle uses at least three colors, so the two-color induced subgraphs are forests. If we denote the acyclic chromatic number of a graph G by , we have that , and in fact every star coloring of G is an acyclic coloring. The star chromatic number has been proved to be bounded on every proper minor closed class by . This results was further generalized by to all low-tree-depth colorings (standard coloring and star coloring being low-tree-depth colorings with respective parameter 1 and 2).
rdf:langString
Звёздная раскраска в теории графов — (правильная) раскраска вершин, в которой любой путь из четырёх вершин использует как минимум три различных цвета. Эквивалентное определение — это такая раскраска, при которой любые компоненты связности порождённых подграфов, образованных вершинами любых двух цветов, являются звёздами. Звёздная раскраска была предложена Грюнбаумом. Звёздное хроматическое число графа — это минимальное число цветов, необходимых для получения звёздной раскраски . Одно из обобщений звёздной раскраски тесно связано с концепцией ациклической раскраски графа, в которой требуется, чтобы любой цикл использовал по меньшей мере три цвета, так что порождённые парой цветов подграфы образуют леса. Хроматическое число графа не превосходит звёздное хроматическое число , что фактически означает, что любая звёздная раскраска графа является ациклической раскраской. Доказано, что звёздное хроматическое число ограничено для любого минорно замкнутого класса. Этот результат позднее был обобщён для всех раскрасок с малой глубиной деревьев (обычная раскраска и звёздная раскраска являются раскрасками с малой глубиной деревьев с параметрами 1 и 2 соответственно). Было показано, что проверка выполнения неравенства , является NP-полной задачей, даже если граф одновременно и планарен, и двудолен.Коулмэн и Морэ показали, что поиск оптимальной звёздной раскраски является NP-трудной задачей, даже если является двудольным графом.
xsd:nonNegativeInteger
4844
