BERGES CONJECTURE FOR CUBIC GRAPHS WITH SMALL COLOURING DEFECT JAN KARAB AˇS EDITA M AˇCAJOV A ROMAN NEDELA AND MARTIN ˇSKOVIERA

2025-05-06 0 0 717.8KB 20 页 10玖币

侵权投诉

BERGE’S CONJECTURE FOR CUBIC GRAPHS

WITH SMALL COLOURING DEFECT

J´

AN KARAB ´

Aˇ

S, EDITA M ´

Aˇ

CAJOV ´

A, ROMAN NEDELA, AND MARTIN ˇ

SKOVIERA

Dedicated to professor J´an Plesn´ık, our teacher and colleague.

Abstract. A long-standing conjecture of Berge suggests that every bridgeless

cubic graph can be expressed as a union of at most ﬁve perfect matchings.

This conjecture trivially holds for 3-edge-colourable cubic graphs, but remains

widely open for graphs that are not 3-edge-colourable. The aim of this paper is

to verify the validity of Berge’s conjecture for cubic graphs that are in a certain

sense close to 3-edge-colourable graphs. We measure the closeness by looking

at the colouring defect, which is deﬁned as the minimum number of edges left

uncovered by any collection of three perfect matchings. While 3-edge-colourable

graphs have defect 0, every bridgeless cubic graph with no 3-edge-colouring has

defect at least 3. In 2015, Steﬀen proved that the Berge conjecture holds for

cyclically 4-edge-connected cubic graphs with colouring defect 3 or 4. Our aim is

to improve Steﬀen’s result in two ways. We show that all bridgeless cubic graphs

with defect 3 satisfy Berge’s conjecture irrespectively of their cyclic connectivity.

If, additionally, the graph in question is cyclically 4-edge-connected, then four

perfect matchings suﬃce, unless the graph is the Petersen graph. The result

is best possible as there exists an inﬁnite family of cubic graphs with cyclic

connectivity 3 which have defect 3 but cannot be covered with four perfect

matchings.

1. Introduction

In 1970’s, Claude Berge made a conjecture that every bridgeless cubic graph G

can have its edges covered by at most ﬁve perfect matchings (see [23]). The

corresponding set of matchings is called a Berge cover of G.

Berge’s conjecture relies on the fact that every preassigned edge of Gbelongs to

a perfect matching, and hence there is a set of perfect matchings that cover all the

edges of G. The smallest number of perfect matchings needed for this purpose is

the perfect matching index of G, denoted by π(G). Clearly, π(G) = 3 if and only

if Gis 3-edge-colourable, so if Ghas chromatic index 4, then the value of π(G)

is believed to be either 4 or 5. In this context it may be worth mentioning that

π(P g) = 5, where P g denotes the Petersen graph, and that cubic graphs with

π= 5 are very rare [3, 21].

2020 Mathematics Subject Classiﬁcation. 05C15, 05C70 (Primary); 05C75 (Secondary).

Key words and phrases. perfect matching, Berge’s conjecture, snark.

arXiv:2210.13234v3 [math.CO] 9 Jan 2025

2 J. KARAB ´

Aˇ

S, E. M ´

Aˇ

CAJOV ´

A, R. NEDELA, AND M. ˇ

SKOVIERA

Berge’s conjecture is closely related to a stronger and arguably more famous

conjecture of Fulkerson [10], attributed also to Berge and therefore often referred

to as the Berge-Fulkerson conjecture [26]. The latter conjecture suggests that

every bridgeless cubic graph contains a collection of six perfect matchings such

that each edge belongs to precisely two of them. Fulkerson’s conjecture clearly

implies Berge’s. Somewhat surprisingly, the converse holds as well, which follows

from an ingenious construction due to Mazzuoccolo [23].

Very little is known about the validity of either of these conjectures. Besides

the 3-edge-colourable cubic graphs, the conjectures are known to hold only for a

few classes of graphs, mostly possessing a very speciﬁc structure (see [5, 9, 11, 12,

17, 22, 29]). On the other hand, it has been proved that if Fulkerson’s conjecture

is false, then the smallest counterexample would be cyclically 5-edge-connected

(M´aˇcajov´a and Mazzuoccolo [20]).

In this paper we investigate Berge’s conjecture under more general assumptions,

not relying on any speciﬁc structure of graphs: our aim is to verify the conjecture

for all cubic graphs that are, in a certain sense, close to 3-edge-colourable graphs.

In our case, the proximity to 3-edge-colourable graphs will be measured by the

value of their colouring defect. The colouring defect of a cubic graph, or just defect

for short, is the smallest number of edges that are left uncovered by any set of three

perfect matchings. This concept was introduced and thoroughly studied by Steﬀen

[28] in 2015 who used the notation µ3(G) but did not coin any term for it. Since

a cubic graph has defect 0 if and only if it is 3-edge-colourable, colouring defect

can serve as a measure of uncolourability of cubic graphs, along with resistance,

oddness, and other similar invariants recently studied by a number of authors, see

for example [1, 2, 8].

In [28, Corollary 2.5] Steﬀen proved that the defect of every bridgeless cubic

graph that cannot be 3-edge-coloured is at least 3, and can be arbitrarily large.

He also proved that every cyclically 4-edge-connected cubic graph with defect 3

or 4 satisﬁes Berge’s conjecture [28, Theorem 2.14].

We strengthen the latter result in two ways.

First, we show that every bridgeless cubic graph with defect 3 satisﬁes the Berge

conjecture irrespectively of its cyclic connectivity.

Theorem 1.1. Every bridgeless cubic graph with colouring defect 3admits a Berge

cover.

Second, we prove that if a graph with colouring defect 3 is cyclically 4-edge-

connected, then four perfect matchings are enough to cover all its edges, except

for the Petersen graph.

Theorem 1.2. Let Gbe a cyclically 4-edge-connected cubic graph with defect 3.

Then π(G)=4, unless Gis the Petersen graph.

BERGE’S CONJECTURE FOR CUBIC GRAPHS. . . 3

As we shall see later, Theorem 1.2 is best possible in the sense that there exist

inﬁnitely many 3-connected cubic graphs with colouring defect 3 that cannot be

covered with four perfect matchings.

The existence of a cover with four perfect matchings is known to have a number

of important consequences. For example, such a graph satisﬁes the Fan-Raspaud

conjecture [7], admits a 5-cycle double cover and has a cycle cover of length 4/3·m,

where mis the number of edges [28, Theorem 3.1].

Our proofs use a wide range of methods. Both main results rely on Theorem 4.1

which describes the structure of a subgraph resulting from the removal of a 6-edge-

cut from a bridgeless cubic graph. Moreover, the proof of Theorem 1.2 establishes

an interesting relationship between the colouring defect and the bipartite index of

a cubic graph. We recall that the bipartite index of a graph is the smallest number

of edges whose removal yields a bipartite graph. This concept was introduced by

Thomassen in [30] and was applied in [30, 31] in a diﬀerent context.

Our paper is organised as follows. The next section summarises deﬁnitions and

results needed for understanding the rest of the paper. Section 3 provides a brief

account of the theory surrounding the notion of colouring defect. Speciﬁc tools

needed for the proofs of Theorems 1.1 and 1.2 are established in Section 4. The two

theorems are proved in Sections 5 and 6, respectively. The ﬁnal section illustrates

that the condition on cyclic connectivity in Theorem 1.2 cannot be removed.

2. Preliminaries

2.1. Graphs. Graphs studied in this paper are ﬁnite and mostly cubic (that

is, 3-valent). Multiple edges and loops are permitted. The order of a graph G,

denoted by |G|, is the number of its vertices. A circuit in Gis a connected 2-

regular subgraph of G. A k-cycle is a circuit of length k. The girth of Gis the

length of a shortest circuit in G.

An edge cut is a set Rof edges of a graph whose deletion yields a disconnected

graph. A common type of an edge cut arises by taking a subset of vertices or

an induced subgraph Hof Gand letting Rto be the set δG(H) of all edges with

exactly one end in H. We omit the subscript Gwhenever Gis clear from the

context.

A connected graph Gis said to be cyclically k-edge-connected for some integer

k≥1 if the removal of fewer than kedges cannot leave a subgraph with at least two

components containing circuits. The cyclic connectivity of Gis the largest integer

knot exceeding the cycle rank of Gsuch that Gis cyclically k-edge-connected

(recall that cycle rank is also known as Betti number or cyclomatic number, see

[6, Chapter 1.9]). An edge cut Rin Gthat separates two circuits from each other

is cycle-separating. It is not diﬃcult to see that the set δG(C) leaving a shortest

circuit Cof a cubic graph Gis cycle-separating unless Gis the complete bipartite

graph K3,3, the complete graph K4, or the 3-dipole, the graph which consists of

4 J. KARAB ´

Aˇ

S, E. M ´

Aˇ

CAJOV ´

A, R. NEDELA, AND M. ˇ

SKOVIERA

two vertices and three parallel edges joining them. Observe that an edge cut

formed by a set of independent edges is always cycle-separating. Conversely, a

cycle-separating edge cut of minimum size is independent.

2.2. Edge colourings and ﬂows. An edge colouring of a graph Gis a mapping

from the edge set of Gto a set of colours. A colouring is proper if any two edge-

ends incident with the same vertex receive distinct colours. A k-edge-colouring is

a proper edge colouring where the set of colours has kelements. Unless speciﬁed

otherwise, our colouring will be assumed to be proper and graphs to be subcubic,

that is, with vertices of valency 1, 2, or 3.

There is a standard method of transforming a 3-edge-colouring to another 3-

edge-colouring: it uses so-called Kempe switches: Let Gbe a subcubic graph

endowed with a proper 3-edge-colouring σ. Take two distinct colours iand jfrom

{1,2,3}. An (i, j)-Kempe chain in G(with respect to σ) is a non-extendable

walk Lthat alternates edges coloured iwith those coloured j. It is easy to see

that Lis either a bicoloured circuit or path starting and ending at the vertex of

valency smaller than 3. The Kempe switch along a Kempe chain produces a new

3-edge-colouring of Gby interchanging the colours on L.

It is often useful to regard 3-edge-colourings of cubic graphs as nowhere-zero

ﬂows. To be more precise, one can identify each colour from the set {1,2,3}with

its binary representation; thus 1 = (0,1), 2 = (1,0), and 3 = (1,1). Having done

this, the condition that the three colours meeting at every vertex vare all distinct

becomes equivalent to requiring the sum of the colours at vto be 0 = (0,0) in

Z2×Z2. The latter is nothing but the Kirchhoﬀ law for nowhere-zero Z2×Z2-ﬂows.

Recall that an A-ﬂow on a graph Gis a pair (D, ϕ) where ϕis an assignment of

elements of an abelian group Ato the edges of G, and Dis an assignment of one

of two directions to each edge in such a way that, for every vertex vin G, the sum

of values ﬂowing into vequals the sum of values ﬂowing out of v(Kirchhoﬀ’s law).

Anowhere-zero A-ﬂow is one which does not assign 0 ∈Ato any edge of G. If

each element x∈Asatisﬁes x=−x, then Dcan be omitted from the deﬁnition.

It is well known that the latter is satisﬁed if and only if A∼

=Zn

2for some n≥1.

The following well-known statement is a direct consequence of Kirchhoﬀ’s law.

Lemma 2.1. (Parity Lemma) Let Gbe a graph with maximum degree 3endowed

with a proper 3-edge-colouring ξ. If His a subgraph of Gsuch that every vertex

of His trivalent in G, then

e∈δG(H)

ξ(e) = 0.

Equivalently, the number of edges in δG(H)carrying any ﬁxed colour has the same

parity as the size of the cut.

A cubic graph Gis said to be colourable if it admits a 3-edge-colouring. A

2-connected cubic graph that admits no 3-edge-colouring is called a snark. Our

deﬁnition agrees with that of Cameron et al. [4], Nedela and ˇ

Skoviera [24], Steﬀen

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

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

10 玖币 0人已下载

立即下载

摘要：

BERGE’SCONJECTUREFORCUBICGRAPHSWITHSMALLCOLOURINGDEFECTJ´ANKARAB´AˇS,EDITAM´AˇCAJOV´A,ROMANNEDELA,ANDMARTINˇSKOVIERADedicatedtoprofessorJ´anPlesn´ık,ourteacherandcolleague.Abstract.Along-standingconjectureofBergesuggeststhateverybridgelesscubicgraphcanbeexpressedasaunionofatmostfiveperfectmatchings....

展开>> 收起<<

BERGES CONJECTURE FOR CUBIC GRAPHS WITH SMALL COLOURING DEFECT JAN KARAB AˇS EDITA M AˇCAJOV A ROMAN NEDELA AND MARTIN ˇSKOVIERA.pdf

共20页,预览4页

还剩页未读，继续阅读

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

BERGES CONJECTURE FOR CUBIC GRAPHS WITH SMALL COLOURING DEFECT JAN KARAB AˇS EDITA M AˇCAJOV A ROMAN NEDELA AND MARTIN ˇSKOVIERA

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: