Снарки: графы без 3-раскраски рёбер

Введение

3-регулярный граф, не имеющий 3-крайней раскраски – термин теории графов.

В математической области теории графов, снарк – это неориентированный граф с ровно тремя ребрами на вершину, ребра которого нельзя раскрасить только тремя цветами. Чтобы избежать тривиальных случаев, снарки часто ограничиваются дополнительными требованиями к их связности и длине циклов. Существует бесконечно много снарков. Одна из эквивалентных формулировок теоремы о четырех красках утверждает, что каждый снарк является непланарным графом. Исследования снарков начались с работы Питера Г. Тайта над теоремой о четырех красках в 1880 году, но их название появилось гораздо позже, данное им Мартином Гарднером в 1976 году. Помимо раскраски, снарки также связаны с другими сложными задачами в теории графов: в статье, опубликованной в Electronic Journal of Combinatorics, Мирослав Хладный и Мартин Шковиера отмечают, что

наряду с упомянутыми проблемами, гипотеза снарков В. Т. Тютте касается существования графов Петерсена в качестве миноров снарков; доказательство этой гипотезы давно анонсировано, но остается неопубликованным и решило бы частный случай существования 4-потоков без нулей.

Определение

Точное определение снарков варьируется у разных авторов, но обычно относится к кубическим графам (имеющим ровно три ребра на каждой вершине), чьи ребра нельзя раскрасить только тремя цветами. Согласно теореме Визинга, количество цветов, необходимых для ребер кубического графа, равно либо трем («графы первого класса»), либо четырем («графы второго класса»), поэтому снарки являются кубическими графами второго класса. Однако, чтобы избежать случаев, когда снарк относится ко второму классу по тривиальным причинам или строится тривиальным образом из меньших графов, часто накладываются дополнительные ограничения на связность и длину циклов. В частности: если кубический граф имеет мост, ребро, удаление которого разъединит его, то он не может быть графом первого класса. По лемме о пожатиях рук, подграфы по обе стороны моста имеют нечетное число вершин каждый. Какой бы из трех цветов ни был выбран для моста, их нечетное число вершин препятствует покрытию этих подграфов циклами, чередующимися между двумя другими цветами, как это потребовалось бы при раскраске ребер в три цвета. По этой причине снарки обычно требуют быть безмостными. Петля (ребро, соединяющее вершину с самой собой) не может быть раскрашена без появления одного и того же цвета дважды на этой вершине, что является нарушением обычных требований к раскраске ребер графа. Кроме того, цикл, состоящий из двух вершин, соединенных двумя ребрами, всегда можно заменить одним ребром, соединяющим их двух других соседей, упрощая граф без изменения его возможности раскраски ребер в три цвета. По этим причинам снарки обычно ограничиваются простыми графами, графами без петель или кратных ребер. Если граф содержит треугольник, его можно снова упростить, не изменяя его возможности раскраски ребер в три цвета, путем стягивания трех вершин треугольника в одну вершину. Поэтому многие определения снарков запрещают треугольники. Однако, хотя это требование также упоминалось в работе Гарднера, давшей название «снарк» этим графам, Гарднер включает граф Тиеце, содержащий треугольник, в список снарков. Если граф содержит четырехвершинный цикл, его можно упростить двумя различными способами, удалив два противоположных ребра цикла и заменив полученные пути из вершин степени два одиночными ребрами. Он имеет раскраску ребер в три цвета тогда и только тогда, когда хотя бы одно из этих упрощений имеет такую раскраску. Поэтому Айзекс требует, чтобы «нетривиальный» кубический граф второго класса не содержал четырехвершинных циклов, и другие авторы последовали его примеру, запретив эти циклы. Требование, чтобы снарк избегал циклов длиной четыре или меньше, можно обобщить, указав, что обхват этих графов, длина их кратчайших циклов, составляет не менее пяти. Более строго, определение, используемое в [название работы], требует, чтобы снарки были циклически 4-реберно связными. Это означает, что не может существовать подмножества из трех или менее ребер, удаление которых разъединит граф на два подграфа, каждый из которых содержит по крайней мере один цикл. Бринкманн и др. определяют снарк как кубический и циклически 4-реберно связный граф с обхватом пять или более и принадлежащий ко второму классу; они определяют «слабый снарк», допускающий обхват четыре. Хотя эти определения учитывают ограничения на обхват до пяти, существуют снарки с произвольно большим обхватом.

The precise definition of snarks varies among authors, but generally refers to cubic graphs (having exactly three edges at each vertex) whose edges cannot be colored with only three colors. By Vizing's theorem, the number of colors needed for the edges of a cubic graph is either three ("class one" graphs) or four ("class two" graphs), so snarks are cubic graphs of class two. However, in order to avoid cases where a snark is of class two for trivial reasons, or is constructed in a trivial way from smaller graphs, additional restrictions on connectivity and cycle lengths are often imposed. In particular:
If a cubic graph has a bridge, an edge whose removal would disconnect it, then it cannot be of class one. By the handshaking lemma, the subgraphs on either side of the bridge have an odd number of vertices each. Whichever of three colors is chosen for the bridge, their odd number of vertices prevents these subgraphs from being covered by cycles that alternate between the other two colors, as would be necessary in a 3 edge coloring. For this reason, snarks are generally required to be bridgeless. A loop (an edge connecting a vertex to itself) cannot be colored without causing the same color to appear twice at that vertex, a violation of the usual requirements for graph edge coloring. Additionally, a cycle consisting of two vertices connected by two edges can always be replaced by a single edge connecting their two other neighbors, simplifying the graph without changing its three edge colorability. For these reasons, snarks are generally restricted to simple graphs, graphs without loops or multiple adjacencies. If a graph contains a triangle, then it can again be simplified without changing its three edge colorability, by contracting the three vertices of the triangle into a single vertex. Therefore, many definitions of snarks forbid triangles. However, although this requirement was also stated in Gardner's work giving the name "snark" to these graphs, Gardner lists Tietze's graph, which contains a triangle, as being a snark. If a graph contains a four vertex cycle, it can be simplified in two different ways by removing two opposite edges of the cycle and replacing the resulting paths of degree two vertices by single edges. It has a three edge coloring if and only if at least one of these simplifications does. Therefore, Isaacs requires a "nontrivial" cubic class two graph to avoid four vertex cycles, and other authors have followed suit in forbidding these cycles. The requirement that a snark avoid cycles of length four or less can be summarized by stating that the girth of these graphs, the length of their shortest cycles, is at least five. More strongly, the definition used by requires snarks to be cyclically 4 edge connected. That means there can be no subset of three or fewer edges, the removal of which would disconnect the graph into two subgraphs each of which has at least one cycle. Brinkmann et al. define a snark to be a cubic and cyclically 4 edge connected graph of girth five or more and class two; they define a "weak snark" to allow girth four. Although these definitions only consider constraints on the girth up to five, snarks with arbitrarily large girth exist.

Свойства

Работа Питера Г. Тайта установила, что теорема о четырех красках верна тогда и только тогда, когда каждый снарк непланарен. Эта теорема утверждает, что любой планарный граф допускает раскраску его вершин четырьмя цветами, но Тейт показал, как преобразовать 4-раскраски вершин максимальных планарных графов в 3-раскраски ребер их двойственных графов, которые являются кубическими и планарными, и наоборот. Следовательно, планарный снарк обязательно был бы двойственным графом к контрпримеру теоремы о четырех красках. Таким образом, последующее доказательство теоремы о четырех красках также демонстрирует, что все снарки непланарны. Все снарки негамильтоновы: если кубический граф имеет гамильтонов цикл, всегда можно раскрасить его ребра, используя два цвета поочередно для цикла и третий цвет для оставшихся ребер. Однако многие известные снарки близки к гамильтоновым, в том смысле, что они являются гипогамильтоновыми графами: удаление любой отдельной вершины оставляет гамильтонов подграф. Гипогамильтонов снарк должен быть бикритическим: удаление любых двух вершин оставляет подграф, допускающий 3-раскраску ребер. Нечетность кубического графа определяется как минимальное количество нечетных циклов в любой системе циклов, покрывающей каждую вершину ровно один раз (2-фактор). По той же причине, что у них нет гамильтоновых циклов, снарки обладают положительной нечетностью: полностью четный 2-фактор привел бы к 3-раскраске ребер, и наоборот. Возможно построить бесконечные семейства снарков, чья нечетность линейно растет с числом их вершин. Гипотеза о двойном покрытии циклами утверждает, что в любом связном графе без мостов можно найти набор циклов, покрывающих каждое ребро дважды, или, эквивалентно, что граф можно вложить на поверхность таким образом, что все грани вложения являются простыми циклами. Если кубический граф имеет 3-раскраску ребер, он имеет двойное покрытие циклами, состоящее из циклов, образованных каждой парой цветов. Следовательно, среди кубических графов, снарки являются единственными возможными контрпримерами. В более общем смысле, снарки представляют собой сложный случай для этой гипотезы: если она верна для снарков, то она верна для всех графов. В этой связи Бранко Грюнбаум предположил, что ни один снарк не может быть вложен на поверхность таким образом, чтобы все грани были простыми циклами и чтобы каждые две грани либо были непересекающимися, либо имели только одно общее ребро; если бы какой-либо снарк имел такое вложение, его грани образовали бы двойное покрытие циклами. Однако контрпример к гипотезе Грюнбаума был найден Мартином Кохолом. Определение того, является ли заданный циклически 5-связный кубический граф 3-раскрашимым по ребрам, является NP-полной задачей. Следовательно, определение того, является ли граф снарком, является co-NP-полной задачей.

Work by Peter G. Tait established that the four color theorem is true if and only if every snark is non planar. This theorem states that every planar graph has a graph coloring of its the vertices with four colors, but Tait showed how to convert 4 vertex colorings of maximal planar graphs into 3 edge colorings of their dual graphs, which are cubic and planar, and vice versa. A planar snark would therefore necessarily be dual to a counterexample to the four color theorem. Thus, the subsequent proof of the four color theorem also demonstrates that all snarks are non planar. All snarks are non Hamiltonian: when a cubic graph has a Hamiltonian cycle, it is always possible to 3 color its edges, by using two colors in alternation for the cycle, and the third color for the remaining edges. However, many known snarks are close to being Hamiltonian, in the sense that they are hypohamiltonian graphs: the removal of any single vertex leaves a Hamiltonian subgraph. A hypohamiltonian snark must be bicritical: the removal of any two vertices leaves a three edge colorable subgraph. The oddness of a cubic graph is defined as the minimum number of odd cycles, in any system of cycles that covers each vertex once (a 2 factor). For the same reason that they have no Hamiltonian cycles, snarks have positive oddness: a completely even 2 factor would lead to a 3 edge coloring, and vice versa. It is possible to construct infinite families of snarks whose oddness grows linearly with their numbers of vertices. The cycle double cover conjecture posits that in every bridgeless graph one can find a collection of cycles covering each edge twice, or equivalently that the graph can be embedded onto a surface in such a way that all faces of the embedding are simple cycles. When a cubic graph has a 3 edge coloring, it has a cycle double cover consisting of the cycles formed by each pair of colors. Therefore, among cubic graphs, the snarks are the only possible counterexamples. More generally, snarks form the difficult case for this conjecture: if it is true for snarks, it is true for all graphs. In this connection, Branko Grünbaum conjectured that no snark could be embedded onto a surface in such a way that all faces are simple cycles and such that every two faces either are disjoint or share only a single edge; if any snark had such an embedding, its faces would form a cycle double cover. However, a counterexample to Grünbaum's conjecture was found by Martin Kochol. Determining whether a given cyclically 5 connected cubic graph is 3 edge colorable is NP complete. Therefore, determining whether a graph is a snark is co NP complete.

Сначала догадки

В. Т. Тютте предположил, что каждый снарк имеет граф Петерсена как минор. То есть, он предположил, что наименьший снарк, граф Петерсена, может быть получен из любого другого снарка путем стягивания некоторых рёбер и удаления других. Эквивалентно (поскольку граф Петерсена имеет максимальную степень три), каждый снарк имеет подграф, который может быть получен из графа Петерсена путем подразделения некоторых его рёбер. Эта гипотеза является усиленной формой теоремы о четырёх цветах, поскольку любой граф, содержащий граф Петерсена как минор, должен быть непланарным. В 1999 году Нил Робертсон, Дэниел П. Сандерс, Пол Сеймур и Робин Томас объявили о доказательстве этой гипотезы. Отдельные шаги к этому результату были опубликованы, но полное доказательство остаётся неопубликованным. См. гипотезу Хадвигера для других задач и результатов, связывающих раскраску графов и миноры графов. Тютте также предположил обобщение для произвольных графов: каждый связный граф без петерсеновского минора имеет 4-поток без нулей. То есть, рёбрам графа можно присвоить направление и число из множества {1, 2, 3} так, чтобы сумма входящих чисел минус сумма исходящих чисел в каждой вершине делилась на четыре. Как показал Тютте, для кубических графов такое присваивание существует тогда и только тогда, когда рёбра можно раскрасить тремя цветами, поэтому гипотеза следует из гипотезы о снарках в этом случае. Однако доказательство гипотезы о снарках не решит вопрос о существовании 4-потоков для некубических графов.