Total coloring
http://dbpedia.org/resource/Total_coloring an entity of type: Software
Die Totalfärbung ist ein Begriff aus der Graphentheorie und eine Verallgemeinerung sowohl von der Kantenfärbung als auch von der Knotenfärbung.
rdf:langString
In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ″(G) of a graph G is the fewest colors needed in any total coloring of G. Some inequalities for χ″(G): Here Δ(G) is the maximum degree; and ch′(G), the edge choosability. Total coloring conjecture (Behzad, Vizing).
rdf:langString
В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа.Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет. Тотальное хроматическое число χ″(G) графа G — это наименьшее число цветов, необходимых для тотальной раскраски G. Тотальным графом T = T(G) графа G называется граф, в котором При таком определении тотальная раскраска становится (правильной) вершинной раскраской тотального графа. χ″(G) ≤ Δ(G) + 2.
rdf:langString
Тотальне розфарбування в теорії графів — це спосіб розфарбування вершин і ребер графа. В загальному випадку, якщо не сказано іншого, забарвлення завжди вважається правильним в тому сенсі, що немає суміжних ребер та вершин на кінцях ребер, які розфарбовані в один і той же колір.Тотальне хроматичне число χ″(G) графа G — це найменше число кольорів, необхідних для тотального розфарбування G. Тотальним графом T = T(G) графа G називається граф, в якому При такому визначенні тотальне розфарбування стає (правильним) вершинним розфарбуванням тотального графа. Деякі властивості χ″(G): χ″(G) ≤ Δ(G) + 2.
rdf:langString
rdf:langString
Totalfärbung
rdf:langString
Total coloring
rdf:langString
Тотальная раскраска
rdf:langString
Тотальне розфарбування
xsd:integer
690702
xsd:integer
1034422391
rdf:langString
Die Totalfärbung ist ein Begriff aus der Graphentheorie und eine Verallgemeinerung sowohl von der Kantenfärbung als auch von der Knotenfärbung.
rdf:langString
In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ″(G) of a graph G is the fewest colors needed in any total coloring of G. The total graph T = T(G) of a graph G is a graph such that (i) the vertex set of T corresponds to the vertices and edges of G and (ii) two vertices are adjacent in T if and only if their corresponding elements are either adjacent or incident in G. Then total coloring of G becomes a (proper) vertex coloring of T(G). A total coloring is a partitioning of the vertices and edges of the graph into . Some inequalities for χ″(G): 1.
* χ″(G) ≥ Δ(G) + 1. 2.
* χ″(G) ≤ Δ(G) + 1026. (Molloy, Reed 1998) 3.
* χ″(G) ≤ Δ(G) + 8 ln8(Δ(G)) for sufficiently large Δ(G). (Hind, Molloy, Reed 1998) 4.
* χ″(G) ≤ ch′(G) + 2. Here Δ(G) is the maximum degree; and ch′(G), the edge choosability. Total coloring arises naturally since it is simply a mixture of vertex and edge colorings. The next step is to look for any Brooks-typed or Vizing-typed upper bound on the total chromatic number in terms of maximum degree. The total coloring version of maximum degree upper bound is a difficult problem that has eluded mathematicians for 50 years. A trivial lower bound for χ″(G) is Δ(G) + 1. Some graphs such as cycles of length and complete bipartite graphs of the form need Δ(G) + 2 colors but no graph has been found that requires more colors. This leads to the speculation that every graph needs either Δ(G) + 1 or Δ(G) + 2 colors, but never more: Total coloring conjecture (Behzad, Vizing). Apparently, the term "total coloring" and the statement of total coloring conjecture were independently introduced by Behzad and Vizing in numerous occasions between 1964 and 1968 (see Jensen & Toft). The conjecture is known to hold for a few important classes of graphs, such as all bipartite graphs and most planar graphs except those with maximum degree 6. The planar case can be completed if Vizing's planar graph conjecture is true. Also, if the list coloring conjecture is true, then Results related to total coloring have been obtained. For example, Kilakos and Reed (1993) proved that the fractional chromatic number of the total graph of a graph G is at most Δ(G) + 2.
rdf:langString
В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа.Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет. Тотальное хроматическое число χ″(G) графа G — это наименьшее число цветов, необходимых для тотальной раскраски G. Тотальным графом T = T(G) графа G называется граф, в котором 1.
* множество вершин графа T соответствуют вершинам и рёбрам графа G; 2.
* две вершины в T смежны тогда и только тогда, когда соответствующие элементы либо смежны в G, либо инцидентны. При таком определении тотальная раскраска становится (правильной) вершинной раскраской тотального графа. Несколько свойств χ″(G): 1.
* χ″(G) ≥ Δ(G) + 1. 2.
* χ″(G) ≤ Δ(G) + 1026. 3.
* χ″(G) ≤ Δ(G) + 8 ln8(Δ(G)) для достаточно большого Δ(G). 4.
* χ″(G) ≤ ch′(G) + 2. Здесь Δ(G) — это максимальная степень, а ch′(G) — индекс предписанной раскраски рёбер. Тотальная раскраска возникает естественным путём, поскольку она является простым смешением вершинной и рёберной раскрасок.Следующий шаг — это рассмотрение верхних границ тотального хроматического числа в терминах максимальной степени по аналогии с теоремами Брукса или Визинга.Оказалось, что определение верхних границ тотальной раскраски, как функции от максимальной степени, является сложной задачей и ускользает от математиков вот уже 40 лет. Наиболее известная догадка выглядит так: Гипотеза о тотальной раскраске. χ″(G) ≤ Δ(G) + 2. По всей видимости, термин «тотальная раскраска» и формулировку гипотезы независимо предложили и Визинг в многочисленных публикациях между 1964 и 1968 годами (смотри книгу Йенсена и Тофта для деталей). Известно, что гипотеза справедлива для нескольких важных классов графов, таких как двудольные графы и большинство планарных графов, за исключением графов с максимальной степенью 6.Случай планарных графов будет решён, если будет доказано, что гипотеза Визинга о планарных графах верна.Также, если гипотеза о предписанной раскраске рёбер справедлива, то χ″(G) ≤ Δ(G) + 3. Были получены некоторые результаты относительно тотальной раскраски.Например, Килакос и Рид доказали, что дробный хроматический индекс тотального графа для графа G не превосходит Δ(G) + 2. Упомянем также следующую связь рёберного графа и тотального графа: T(G) является эйлеровым в том и только в том случае, когда L(G) эйлеров.
rdf:langString
Тотальне розфарбування в теорії графів — це спосіб розфарбування вершин і ребер графа. В загальному випадку, якщо не сказано іншого, забарвлення завжди вважається правильним в тому сенсі, що немає суміжних ребер та вершин на кінцях ребер, які розфарбовані в один і той же колір.Тотальне хроматичне число χ″(G) графа G — це найменше число кольорів, необхідних для тотального розфарбування G. Тотальним графом T = T(G) графа G називається граф, в якому 1.
* множина вершин графа T відповідає вершинам і ребрам графа G; 2.
* дві вершини T суміжні тоді і тільки тоді, коли відповідні елементи в G або суміжні, або інцидентні. При такому визначенні тотальне розфарбування стає (правильним) вершинним розфарбуванням тотального графа. Деякі властивості χ″(G): 1.
* χ″(G) ≥ Δ(G) + 1. 2.
* χ″(G) ≤ Δ(G) + 1026. 3.
* χ″(G) ≤ Δ(G) + 8 ln8(Δ(G)) для досить великого Δ(G). 4.
* χ″(G) ≤ ch′(G) + 2. Δ(G) — це максимальний степінь, а ch′(G) — . Тотальне розфарбування виникає природним шляхом, оскільки це просто суміш розфарбування вершин і ребер.Наступний крок — це розгляд верхніх меж тотального хроматичного числа в термінах максимальної степені за аналогією теорем Брукса або Візінга.Виявилося, що визначення верхніх меж тотальної розмальовки як функції від максимального степеня є складним завданням, яке залишається нерозв'язаним понад 40 років.Найбільш відома здогадка має такий вигляд. Гіпотеза про тотальну розмальовку. χ″(G) ≤ Δ(G) + 2. Очевидно, термін «тотальне розфарбування» і формулювання гіпотези, незалежно один від одного, запропонували і Візінг у численних публікаціях між 1964 і 1968 роками. (Дивись книгу Йонсена та Тофта для деталей.) Відомо, що гіпотеза справедлива для декількох важливих класів графів, таких як двочасткові графи і більшість планарних графів, за винятком графів з максимальним степенем 6.Випадок планарних графів буде розв'язано, якщо буде доведено, що про планарні графи правильна.Також, якщо справедлива, то χ″(G) ≤ Δ(G) + 3. Відомі деякі результати пов'язані з тотальним розфарбуванням. Наприклад, Кілакос і Рід довели, що дробовий хроматичний індекс тотального графа для графа G не перевершує Δ(G) + 2. Існує зв'язок між реберним графом і тотальним графом:T(G) є ейлеровим тоді і тільки тоді, коли L(G) ейлерів.
xsd:nonNegativeInteger
4470
