Monochromatic Cycles and Trees in Edge-Colored Complete Graphs∗

CHENG Shuting,WU Baoyindureng

(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)

Abstract: Let f(r,n)be the maximum integer k such that every r-edge-colored complete graph Kn contains a monochromatic cycle of length at least k.In 2009,Faudree,Lesniak and Schiermeyer conjectured that every(r+1)-edge-colored complete graphKn contains a monochromatic cycle of length at least for r ≥2.Meanwhile,they also proved that f(2,n) ≥for n ≥6,and this bound is sharp.In 2011,Fujita disproved this conjecture for n=2r and also showed that every r-edge-colored complete graph Kn contains a monochromatic cycle of length at least -for 1 ≤r ≤n.In this paper,we disprove this conjecture for n=rt+1,where r ≥2 and is a positive even integer.More precisely,there exists a(r+1)-edge-colored complete graph Kn contains a monochromatic cycle of length less than-.For a k-edge coloring c of Kn,let moc(Kn,c)be the largest order of monochromatic tree of Kn under c.Let moc(n,k)=min{moc(Kn,c):c is a k-edge coloring of Kn}.We show that for any positive integer n ≥3,moc(n,3)=if n ≡0,1(mod 4)and moc(n,3)=if n ≡2,3(mod 4).

Key words: circumference;edge-colored complete graphs;monochromatic cycles;monochromatic trees

0 Introduction

In this paper,we just use[1]for terminology and notation,so do not define it again,and consider only finite and simple graphs as well as edge-colored graphs withr+1 colors.For an (r+1)-edge-colored complete graphKn,we are concerned with the length of the longest monochromatic cycle.

In 2011,Fujita[2]introduced the following concept and notation.Letf(r,n)be the maximum integerksuch that everyr-edge-colored complete graphKncontains a monochromatic cycle of length at leastk.In 2009,Faudree,Lesniak and Schiermeyer[3]proved thatf(2,n)≥forn≥6 and this bound is sharp.Meanwhile,they proposed the following conjecture:

Conjecture 1[3].

In 2011,Fujita[2]disproved this conjecture forn=2rand showed that everyr-edge-colored complete graphKncontains a monochromatic cycle of length at leastfor 1 ≤r≤n.In particular,f(r,2r+1)=3.

In 2015,Fujita,Lesniak and T´oth[4]investigated the values off(r,n)whennis linear inr.They determined the value off(r,2r+2)for allr≥1 and showed thatf(r,sr+c)=s+1 ifris sufficiently large compared with positive integerssandc.

In this paper,we disprove Conjecture 1 forn=rt+1,wherer≥2,andis a positive even integer.More precisely,there exists a (r+1)-edge-colored complete graphKncontains a monochromatic cycle of length less than-.For ak-edge coloringcofKn,let moc(Kn,c)be the largest order of monochromatic tree ofKnunderc.Let moc(n,k)=min{moc(Kn,c):cis ak-edge coloring ofKn}.We show that for any positive integern≥3,moc(n,3)=ifn≡0,1(mod 4)and moc(n,3)=ifn≡2,3(mod 4).

1 Monochromatic Cycles

LetXandYbe two sets of vertices of a graphG=(V,E).We denote byE[X,Y]the set of edges ofGwith one end inXand the other end inY.IfXis a set of vertices,the induced subgraphG[X]is the subgraph ofGwhose vertex set isXand edge set consists of all edges ofGwhich have both ends inX.IfSis a set of edges,the edge-induced subgraphG[S]is the subgraph ofGwhose edge set isSand vertex set consists of all ends of edges ofS.The circumferencec(G)of a graphGis the length of a longest cycle inG.An edge-colored graph is a graph with each edge assigned a color.Ak-edge-colouringof a graphGis a mappingc:E→I,whereIis a set ofkcolours,in other words,an assignment ofkcolours to the edges ofG.

Fig1 Illustration of the(k+1)-coloring c of Kn

Fig2 Illustration of the(k+1)-coloring c of Kn

LetGibe the edge-induced subgraph ofGinduced by the set of edges assigned colourifor eachi∈{1,···,r+1}.It is obvious that a monochromatic cycle lies inG[Xi∪Yi]ofG1for somei∈{1,···,r}.SinceG[Xi∪Yi]=Kt,thenc(G1)≤t.For eachi∈{1,···,r−1},xis a cut vertex inGi+1.By symmetry,without loss of generality,we assume that a monochromatic cycle lies inG[Xi∪Yj∪Yk]inGi+1forj,k∈{1,···,i−1}.It is no hard to check that the longest monochromatic cycle is even such thatc(Gi+1)≤t.By a similar argument as in the proof ofc(Gi+1),we obtain thatc(Gr+1)≤t.Hence,max{c(G1),···,c(Gr+1)}=.This completes the proof of Theorem 2.

2 Monochromatic Trees

For any 3-edge coloring ofKn,there exists a monochromatic tree of order at least-.It is well-known that for a graphG,at least one ofGandis connected.Equivalently,for any 2-edge coloring of the complete graphKn,there is a monochromatic tree of ordern.A natural question arise:for a positive integerk≥3,what is the order of monochromatic tree in ak-edge coloring ofKn? For ak-edge coloringcofKn,let moc(Kn,c)be the largest order of monochromatic tree ofKnunderc.Let moc(n,k)=min{moc(Kn,c):cis ak-edge coloring ofKn},then by the discussion above,moc(n,2)=nfor any positive integern.Next,we tackle the case whenk=3,and obtain the following result.

Theorem 3For any positive integern≥3,

First,we show that moc(n,3)≤g(n).LetV1,V2,V3,V4be a partition ofKnwith.Now we give a 3-edge coloringcofKnas follows(see Fig3):

Fig3 Illustration of the(k+1)-coloring c of Kn

It is clear that Knhas a monochromatic tree of order g(n) under the coloring c.This shows that moc(n,3)≤g(n).

Next,we show that moc(n,3) ≥g(n).Suppose,on the contrary,that the result is not true,and let c be a 3-edge coloring of Knwith moc(Kn,c)

It is an interesting problem to determine the exact value of moc(n,k) for k ≥4.