Decomposing cubic graphs into isomorphic linear forests Gal KronenbergShoham LetzterAlexey PokrovskiyLiana Yepremyan Abstract

2025-05-06 0 0 932.87KB 49 页 10玖币

侵权投诉

Decomposing cubic graphs into isomorphic linear forests

Gal Kronenberg∗Shoham Letzter†Alexey Pokrovskiy‡Liana Yepremyan§

Abstract

A common problem in graph colouring seeks to decompose the edge set of a given graph into few

similar and simple subgraphs, under certain divisibility conditions. In 1987 Wormald conjectured that

the edges of every cubic graph on 4nvertices can be partitioned into two isomorphic linear forests. We

prove this conjecture for large connected cubic graphs. Our proof uses a wide range of probabilistic

tools in conjunction with intricate structural analysis, and introduces a variety of local recolouring

techniques.

1 Introduction

Many problems in graph theory seek to decompose the edges of a given graph into simpler pieces. A

fundamental example seeks for a decomposition of the edges into matchings, that is, a proper edge-

colouring of a graph. According to a well-known result of Vizing [32] from 1964, the chromatic index of

a graph G, denoted χ′(G) and deﬁned to be the minimum number of matchings needed to decompose the

edges of a simple graph G, is either ∆(G) or ∆(G) + 1. For certain applications, ∆(G) is too large, and

thus there was interest in ﬁnding decompositions into a signiﬁcantly smaller number of pieces, which are

still relatively simple. Perhaps the most famous work in this direction is the Nash-Williams theorem [28]

from 1964 regarding the arboricity of a graph G, namely the minimum number of forests needed in order

to decompose the edges of G. As an interesting interpolation between decompositions into matchings

and into forests, in 1970 Harary [20] suggested to study the minimum number of linear forests needed

to decompose the edges of a given graph G, where a linear forest is a forest whose components are

paths. This parameter is called the linear arboricity of Gand is denoted la(G). Clearly, la(G)≤χ′(G)

for every graph G, as a matching is also a linear forest. A well known conjecture by Akiyama, Exoo,

and Harary from 1980 [4] states that by using linear forests instead of matchings, one can reduce the

number of pieces needed by about a half, namely, that la(G)≤ ⌈∆(G)+1

2⌉. This conjecture is known in

the literature as the linear arboricity conjecture. It is easy to check that the upper bound is tight. Also,

∗Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliﬀe Observatory Quarter, Woodstock Road,

Oxford, United Kingdom. E-mail: kronenberg@maths.ox.ac.uk. Research supported by the European Union’s Horizon

2020 research and innovation programme under the Marie Sk lodowska Curie grant agreement No. 101030925.

†Department of Mathematics, University College London, Gower Street, London WC1E 6BT, UK. Email:

s.letzter@ucl.ac.uk. Research supported by the Royal Society.

‡Department of Mathematics, University College London, Gower Street, London WC1E 6BT, UK. Email:

dralexeypokrovskiy@gmail.com.

§Department of Mathmatics, Emory University, Atlanta, Georgia, 30322, US. Email: lyeprem@emory.edu.

arXiv:2210.11458v3 [math.CO] 20 Jun 2023

since every graph of maximum degree ∆ can be embedded in a ∆-regular graph, an equivalent statement

of the conjecture, which is more commonly studied, is the following.

Conjecture 1.1 (Linear arboricity conjecture; Akiyama, Exoo, and Harary [4]).Every ∆-regular graph

Gsatisﬁes la(G) = ⌈∆+1

2⌉.

The case of cubic graphs (3-regular graphs), where the conjecture predicts la(G) = 2, was veriﬁed already

in the paper of Akiyama, Exoo, and Harary [4], and later a shorter proof was presented by Akiyama and

Chv´atal [3] in 1981. In 1988 Alon [7] showed that the linear arboricity conjecture holds asymptotically,

meaning that if Ghas maximum degree at most ∆ then la(G)=∆/2 + o(∆); his o(∆) term was of

order O∆log log ∆

log ∆ . In the same paper Alon also showed that the conjecture holds for graphs with

high girth, that is, when the girth of the graph is Ω(∆). Subsequently, using Alon’s approach, the linear

arboricity conjecture was proved to hold for random regular graphs by Reed and McDiarmid [26] in

1990. Alon and Spencer [8] in 1992 improved Alon’s asymptotic error term to O(∆2/3(log ∆)1/3). After

almost thirty years, this error term was very recently improved; at ﬁrst to O(∆2/3−ε), for some absolute

ε > 0 by Ferber, Fox and Jain [15], and ﬁnally to O(√∆(log ∆)4) by Lang and Postle [23]. All of these

approximate results make use of classical probabilistic tools, speciﬁcally, R¨odl’s nibble and Lov´asz’s local

lemma. The result of Lang and Postle also apply to yet another folklore conjecture in graph theory,

known as the list colouring conjecture, tying the two conjectures together. This conjecture asserts that

if Lassigns a list of ∆(G) + 1 colours to each edge of G, then there is a proper edge-colouring of G

where each edge uses a colour from its list. This conjecture emerged in 1970-80’s, and was researched

by prominent mathematicians, including Kahn [22] and Molloy and Reid [27].

Apart from approximate results and random regular graphs, the linear arboricity conjecture was veriﬁed

for d∈ {3,4}[3,4,5], d∈ {5,6}[13,29,31], d= 8 [14], d= 10 [19], as well as for various other families

of graphs such as complete graphs, complete bipartite graphs, trees, planar graphs, some k-degenerate

graphs and binomial random graphs [4,5,11,14,18,19,34,35]. However, in its full generality the

conjecture still remains open.

As we have seen, the linear arboricity conjecture is known to hold for cubic graphs. It was thus asked

whether it can be strengthened for such graphs. One such strengthening is the following conjecture,

made by Wormald [33] in 1987, asking not only for a decomposition into two linear forests, but also

requires them to be “balanced”.

Conjecture 1.2 (Wormald).The edges of any cubic graph, whose number of vertices is divisible by 4,

can be 2-edge-coloured such that the two colour classes are isomorphic linear forests.

Prior to our work, Wormald’s Conjecture was known to be true only for some very speciﬁc cubic graphs.

It was proved for Jaeger graphs in work of Bermond, Fouquet, Habib and P´eroche [16] and Wormald [33],

and for some further classes of cubic graphs by Fouquet, Thuillier, Vanherpe and Wojda [17].

In our current work, we essentially settle this conjecture.

Theorem 1.3. Let Gbe a connected cubic graph on nvertices, where nis large and divisible by 4. Then

there is a red-blue colouring of the edges of Gwhose colour classes span isomorphic linear forests.

We note that our proof can be modiﬁed to relax the requirement of Gbeing connected to Ghaving at

least one large connected component, meaning a component of size at least a certain (large) universal

constant. This strengthening is described in the concluding section, Section 9. In addition, our proof

can be modiﬁed to show that if the number of vertices is not divisible by 4 then we can guarantee that

the two linear forests are isomorphic up to removing or adding an edge. Speciﬁcally, we can guarantee

that the only diﬀerence in component structure is that the red graph has two extra edge components,

and the blue graph has one extra component which is a path of length 3.

It is worth mentioning that, although our proof of Conjecture 1.2 is quite long and involved, we can

prove the following approximate version of Warmald’s conjecture with a fairly short and neat proof (note

that here we do not require divisibility or connectivity).

Theorem 1.4. Let Gbe a cubic graph on nvertices, where nis large. Then Gcan be red-blue coloured

so that all monochromatic components are paths of length O(log n), and the numbers of red and blue

components which paths of length tdiﬀer by at most n2/3, for every t≥1.

This approximate version is proved in Section 3(this is a special case of Lemma 3.3), where the rest of

the paper (from Section 4onwards) is dedicated to proving Theorem 1.3 using Lemma 3.3.

We sketch the proof of Theorem 1.3 in great detail in the next section, but here is a quick summary.

The starting point of the proof of Theorem 1.3 is Theorem 1.4, and as such, we now brieﬂy sketch the

proof of the latter, approximate theorem. One natural way to split a cubic graph into almost isomorphic

parts is to colour each edge either red or blue uniformly at random and independently. However, the

two colour classes will have many vertices of degree 3, and will thus be far from being a linear forest.

To get a colouring which is both balanced with high probability, and whose colour classes are “close”

to being linear forests, instead of using the random colouring described above, we use a semi-random

colouring scheme whose colour classes have maximum degree at most 2. Before describing how we do

so, we point out that this is not the end of the road; we still need to eliminate monochromatic cycles

and long monochromatic paths. Doing so requires some clever tricks, which achieve these goals using

local steps, without harming the nice properties we have achieved, and without introducing too many

dependencies.

For the semi-random colouring, we start with a 2-colouring of Gwhere each monochromatic component

is a path, and recolour each path randomly and independently, reminiscently of Kempe-changes. For

technical reasons (related to the concentration inequality which we apply at the end), we need every

monochromatic component in the initial colouring to be a short path. This can be achieved through a

well-known result of Thomassen [30].

In 1984, Bermond, Fouquet, Habib, and P´eroche [10] conjectured that not only can every cubic graph be

decomposed into two linear forests, but it can be done in such a way that every path in each of the two

linear forests has length at most 5. In 1996 Jackson and Wormald [21] proved this conjecture with the

constant 18 instead of 5. Later this was improved by Aldred and Wormald [6] to 9, and the conjecture

was ﬁnally resolved in 1999 by Thomassen [30].

Theorem 1.5 (Thomassen).Any cubic graph can be 2-edge-coloured such that every monochromatic

component is a path of length at most ﬁve.

We will, in fact, prove a more general statement than the one in Theorem 1.4 (see Lemma 3.3) that

is applicable also for cubic graph with a given partial colouring with nice properties. This will allow

us to pre-colour small parts of the graph in advance and obtain an “almost balanced” colouring which

preserves large parts of the pre-colouring. The pre-coloured subgraph will contain many “gadgets”,

which are small subgraphs with two colourings with the property that, by replacing one colouring by

the other, the diﬀerence between the number of red and blue components which are paths of a given

length ℓdecreases by 1, and the numbers of longer monochromatic components does not change. Since

Lemma 3.3 guarantees that many gadgets for each relevant ℓsurvive, we can use them straightforwardly

to correct the imbalance between red and blue component counts.1

Finding gadgets that interact well with the rest of the graph is a pretty subtle process, as we need to

consider not only the various diﬀerent forms the structure of the gadget itself can take, but we also need

to consider its neighbourhood, e.g. to make sure that its colouring can be extended to a colouring of

the whole graph where monochromatic components are paths. This is particularly challenging when the

graph contains many short cycles and to overcome this we need sophisticated ways of tracking a certain

colouring process around a geodesic (see Section 8).

We believe that the tools we developed here could provide a new avenue for progress towards the Linear

Arboricity Conjecture.

We will end this section with a short discussion on some related works.

One may wonder about possible vertex analogues of the problems mentioned here. Indeed, this has been

considered before. In 1990 Ando conjectured that the vertices of any cubic graph can be two-coloured

such that the two colour classes induce isomorphic subgraphs. Ando’s conjecture was ﬁrst mentioned

in the paper of Abreu, Goedgebeur, Labbate and Mazzuoccolo [2] where they made an even stronger

conjecture, adding the requirement that the two colour classes induce linear forests. Recently, Das,

Pokrovskiy and Sudakov [12] proved Ando’s conjecture for large connected cubic graphs. In fact, their

proof also veriﬁes the stronger conjecture for cubic graphs of large girth.

Ban and Linial [9] stated an even stronger conjecture (but under some further restrictions on G): the

vertices of every bridgeless cubic graph, except for the Petersen graph, can be 2-vertex-coloured such

that the two colour classes induce isomorphic matchings. This conjecture was proved for some speciﬁc

cubic graphs (see [1,9]), but it is still widely open in general. We discussed this in further details in

Section 9.

2 Proof overview

We now give a detailed sketch of our proof. The main idea is to ﬁrst colour a small part of the graph in a

very structured way, so that it can later be used to make small ﬁxes to the full colouring, and then colour

the rest of the graph in a random way, while guaranteeing that the monochromatic components are (not

too long) paths. Using the randomness, we show that the two colour classes are almost isomorphic.

We then use the pre-coloured graph to ﬁx the imbalance and make the colour classes isomorphic, thus

completing the proof.

The structure of the paper will be as follows. In Section 3we will state and prove Lemma 3.3 about

the existence of an almost-balanced colouring. In section Section 4we will state Lemma 4.2 about the

existence of a good partial colouring, and in Section 4.1 will show how to use Lemma 3.3 and Lemma 4.2

in order to prove Theorem 1.3. In Sections 5to 8we will prove Lemma 4.2.

1Actually, since we can only guarantee gadgets of length o(log n), and the components resulting from Lemma 3.3 can be

longer, we need a separate argument to balance intermediate lengths.

2.1 Notation

Given a graph Gand an edge-colouring χof G, will denote by bG,χ(Pt) and rG,χ(Pt) the number of blue

and red paths of length tin G. For two paths P, Q in a graph G, we denote by dG(P, Q) the length of

the shortest path between them. When Gor χare clear from the context, we will skip the corresponding

subscript. In a graph G, a geodesic is deﬁned to be the shortest path between some two vertices. Given

an edge-coloured graph G, we call a vertex monochromatic if all edges incident to it have the same

colour. In this paper log nis the natural logarithm. I am actually not sure think it is of base 2. In a

graph G, we say a subgraph H⊆Gtouches an edge eif ehas exactly one endpoint in H.

2.2 The approximate result

While this is not the ﬁrst step in the process, we now describe an approximate solution of Wormald’s

conjecture, and later explain how to obtain an appropriate partial pre-colouring. For the purpose of this

explanation, our task is to red-blue colour a (large) given cubic graph such that the colour classes are

“almost” isomorphic, that is, the diﬀerence between the number of red and blue components isomorphic

to a path of length tis small, for all t. For this, we wish to colour the graph randomly, while maintaining

certain properties such as the monochromatic components being paths.

Our random colouring will consist of three steps. For the ﬁrst step, we use Thomassen’s result (Theo-

rem 1.5) about the existence of a 2-colouring where each monochromatic component is a path of length

at most 52; we denote the two colours here by purple and green. The ﬁrst random step colours each

purple or green component by one of the two possible alternating red-blue colourings, chosen uniformly

at random and independently. Notice that this random red-blue colouring of Ghas no monochromatic

vertices meaning a vertex who is incident to three edges of the same colour. Moreover, the symmetry

between the colours and the bound on the lengths of purple and green paths would allow us to show

that the colours are, in some sense, close to being isomorphic. However, there is nothing preventing the

appearance of cycles, and we could not rule out the existence of very long monochromatic paths. This

is the more technical part for applying concentration inequalities and doing the ﬁnal re-balancing.

This brings us to the second random step, which will be broken into two parts, and whose purpose is to

eliminate monochromatic cycles. Here, we ﬁrst do something very intuitive: we simply ﬂip the colour of

one edge eCof each monochromatic cycle C, choosing the edge eCuniformly at random and indepen-

dently. Unsurprisingly, while this breaks all monochromatic cycles that existed before the ﬁrst step, new

monochromatic cycles can appear. Luckily, a small ﬁx saves us and eliminates all monochromatic cycles.

The ﬁx essentially consists of re-swapping the colour of eCfor some of the originally monochromatic

cycles C, and swapping the colour of one of the two neighbouring edges of eCin C, while again making

choices randomly and independently.

The next and ﬁnal random step is designed to break “long” paths. After this process monochromatic

paths have length of order O(log n). Here the idea is less intuitive. We let each monochromatic path

Pchoose one of the possibly four boundary edges, that is the edges of the opposite colour that touch

an end of Puniformly at random and independently. Then, for each edge ethat was chosen by two

paths, we ﬂip the colour of ewith probability 1/2, independently. This somewhat strange process has

several beneﬁts: ﬁrst, with high probability, it swaps an edge of each monochromatic path of length at

2The exact constant here is not important. We could even make do with a polylogarithmic bound on the lengths, and,

additionally, we can allow for even cycles, but not odd ones.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

DecomposingcubicgraphsintoisomorphiclinearforestsGalKronenberg∗ShohamLetzter†AlexeyPokrovskiy‡LianaYepremyan§AbstractAcommonproblemingraphcolouringseekstodecomposetheedgesetofagivengraphintofewsimilarandsimplesubgraphs,undercertaindivisibilityconditions.In1987Wormaldconjecturedthattheedgesofeverycub...

展开>> 收起<<

Decomposing cubic graphs into isomorphic linear forests Gal KronenbergShoham LetzterAlexey PokrovskiyLiana Yepremyan Abstract.pdf

共49页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Decomposing cubic graphs into isomorphic linear forests Gal KronenbergShoham LetzterAlexey PokrovskiyLiana Yepremyan Abstract

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: