Recent topics on Monochromatic Structures in Edge-colored Graphs (Designs, Codes, Graphs and Related Areas)

Recent

topics

on

Monochromatic Structures in

Edge-colored Graphs

SHINYA FUJITA*

International College ofArts andSciences

YokohamaCity University

22-2, Seto, Kanazawa-ku, Yokohama, 236-0027,

Japan

fujita yokohama cu.ac.jp

Abstract: Wewill reviewsomerecentresults on theexistenceof monochromatic subgraphs

with certain propertiesinedge-colored graphs.

1

Introduction

We consideronly finiteandsimple graphs. Inparticular, wewill mainlyconsider edge-colored graphs.

Given a graph whose edges are colored, on how many verticescan wefind a monochromatic subgraph

ofacertain type, such

as

aconnected subgraph, or acycle? In this short survey, weshall review some

knownresults and conjecturesregardingthesequestions.

We firstlygive some basicdefinitions. Foragraph$G=(V(G), E(G))$, let$c(G)$ be the

circumference

of$G$, i.e. the length of alongest cyclein$G$. Let $\alpha(G)$ be the independencenumber of$G$, i,e., the size

of the largest independent set of$G$

.

For two disjoint graphs$A$ and$B$, let_$A+B$ be the graph obtained

from $A$ _and $B$ by joining them completely withedges $($thus, $V(A+B)=V(A)\cup V(B),$$E(A+B)=$

$E(A)\cup E(B)\cup\{ab|a\in V(A), b\in V(B)\})$

.

Agraph$G$iscalled _{unicydicif it hasexactly}one_{cycle. Let}

$P_{4}^{+}$ bea $P_{4}$ withtheaddition ofasinglevertex adjacent toaninternal vertex of thepath.

2

Monochromatic

cycles

In thissection, letus consider theproblemoffindingmonochromaticsubgraphs inedge-colored graphs. $A$

first resultinthis directionisthefollowing observation,made along time ago byErd\’osand Rado: A graph

is either connected, orits complement is connected. In otherwords,for every 2-edge-colored complete

graph, there exists a monochromatic spanning connected subgraph (or equivalently, a monochromatic

spanning tree). A substantial generalization of this observation is to ask for the existence of a large

monochromatic subgraph ofacertain type in anedge-colored graph.

Givenanr-edge-colored completegraph,wemay ask for theexistenceofalong monochromatic cycle.

Throughout this section weregard $K_{i}$

as

acycle of order$i$ for_$i\in\{1$,2$\}$

.

Letus consider the following

problem:

Problem 1 Determine the maximum value $f(n, r)$ _{such that every} r-edge-coloring

_of

$K_{n}$ contains a

monochromatic cycle

_of

lengthat least$f(n, r)$

.

In[6] Faudree et al. showed that for everygraph$G$_{of order}$n\geq 6$_{we have}$\max\{c(G), c(\overline{G})\}\geq\lceil 2n/3\rceil,$

where$\overline{G}$

denotes thecomplementof$G$

.

Furthermore,_thisbound issharp. Itcan_beeasilyseenby taking

$G$to be the graph consistingof$\lfloor n/3\rfloor$ isolated vertices andacliqueontheremaining $\lceil 2n/3\rceil$ vertices. So

we have$f(n, 2)=\lceil 2n/3\rceil$

.

For$r\geq 3$, it isknown that $f(n, r)\leq n/(r-1)$.

Thelowerboundon $f(n, r)$is given asfollows:

’Research is supported by the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B) (20740095).

Theorem 2 ([7]) Let $n,$$r$ be integers with _{$n\geq r\geq 1$}

.

Then any r-edge-colored complete graph $K_{n}$

contains amonochromatic cycle

_of

order at least $\lceil n/r\rceil.$ $(i.e., f(n, r)\geq\lceil n/r\rceil.$ $)$

Very recently, Theorem 2 wasslightlyimproved in

some

specialcases:

Theorem 3 ([10]) Let$n,$$r$ beintegers with$n\geq r\geq 1$. Suppose that both$n$ and $r\frac{n(n-1)-2r}{(n-2)r}\rceil$ are even.

Then any r-edge-coloredcompletegraph$K_{n}$ containsa monochromatic cycle

of

order atleast $r\frac{n(n-1)-2r}{(n-2)r}\rceil.$

Another recent progressonthis problemis the following:

Theorem 4 ([11]) The followingstatements hold:

(i) $Forn\geq r\geq 3,$ $f(2r+2, r)=3.$

(ii) For anypositive integers $s,$$c$ with $s\geq 2,$ $c\geq 2,$ $f(sr+c, r)=s+1$ holds

if

$r$ is suficiently large

comparedwith$s$ and$c.$

This theorem saysthat there exist infinitely manypairs $n,$$r$ suchthat $f(n, r)=\lceil n/r\rceil$

.

But we do

not know theexact value of$f(n, r)$ inothercases. Even for the case $f(n, 3)$,it isopen.

3

Gallai-colorings and

extensions

In thistopic, we shall consider the task of finding monochromatic subgraphs in edge-colored complete

graphs by putting a restriction on the edge-coloring. Edge colorings of complete graphs in which no

triangle is colored with three distinct colorswere called Gallai-partitions in [25], and Gallai-coloringsin

[20, 21]. Herewebrieflycall these colorings$G$-colorings andalwaysassume that $G$-colorings are onthe

edges ofa complete graph. More thanjust the term, the concept occursin relationto deep structural

properties offundamental objects. An important result, Theorem 5, from Gallai’s original paper [17]

-translatedto English and endowed bycommentsin [26] - canbe reformulated interms of$G$-colorings.

Further occurrences are related to generalizations of the perfect graph theorem [2, 3], Ramsey-type

functions called Gallai-Ramsey numbers [13, 16], or applications ininformationtheory [24].

Our starting point in this section is the following result ofGallai [17], see anexplicit proof in [20].

Wesay thata color class of anedge-coloringof$G$is connectedif it together with allverticesof$G$forms

aconnectedgraph. Otherwise the color classiscalled disconnected.

Theorem5 In every $G$-coloring with at least three colors, at least one

of

the color classes must be

disconnected.

What is the role offorbidding arainbow triangle? Call asubgraph rainbow ifallcolorsonthe edges

ofthe subgraphare distinct. Can weextendTheorem5insomewaytocolorings wherearainbow copy of

someotherfixedgraph$F$isforbidden? Thisquestionisthe centraltopicof this section. Anedge coloring

ofacomplete graph$K$_{is connectedif}every_{color classin}$K$_{is connected. Let us say that agraph}$F$has

the disconnectionproperty, $DP$, ifthereexists a natural number $m=m(F)$ (notethat $m(F)$ _{does not}

dependon the order of$K$)suchthat the following holds: ineveryedgecoloring ofa complete graphwith

at least $m$ colors, either there is a rainbow $F$or at least one color classis disconnected. Equivalently,

$F$ _{has the} disconnection _{property if, in} every connected coloring_with at least _{$m(F)$ colors, there is} a

rainbow copyof$F$

.

Notice that _{$m(F)\geq|E(F)|$} because complete graphs whichare large enough have

connected colorings using $|E(F)|-1$ colors with no rainbow$F.$

By definition, Theorem5 tells usthat $K_{3}\in DP$. In [12] $K_{1}+(K_{1}\cup K_{2})\in DP$isshown. Therecent

progress on this topicis thefollowing:

Theorem6 ([9]) The following statements hold:

(i)

_If

$F\in DP$ is connected and bipartite, then$Fi_{\mathcal{S}}$a tree

or a unicyclic graph or two such components

(ii) For any$F\in DP$, there exists an edge $e\in E(F)$ such that$F-e$ is bipartite.

(iii)

_If

$F\in DP$is connected, then$F$ can_be obtained

from

a tree byadding at most two edges.

(iv)

_If

$F$ _is a unicyclic graphsuch thatitscycle is a triangle, then$F\in DP$

.

(hence, any

_forest

belongs

to $DP.)$

Wedo not know whether smallcycleswithat least4verticesarein$DP$_{. So}wepropose the following

problem:

Problem 7 Is $C_{4}\in DP^{9}$ More generally, areeven cycles in$DP^{9}$

In [9] the authorsconstruct anexamplewhich shows that if$C_{4}\in DP$then$m(C_{4})>4(=|E(C_{4})$

4

Covering by monochromatic subgraphs and

related

topics

So far, much work has been done oncovering problems in edge-coloredcomplete graphs. Thosecome

from avarietyof background, butmostly the purposeinthistopicis tocoverthe whole vertex set of$K_{n}$

by monochromatic connected components. One such example isthe following, which is the equivalent

formulation of theRyser’sconjecture onmulti-partitehypergraphs [22,27]:

Conjecture8 In everyr-edge-coloring

_of

acomplete graph, thevertexset canbe covered by the vertices

of

at most$r-1$ monochromatic connected components.

Thisconjecture is open for $r\geq 6$

.

It is trivially true for_$r=2$, the

cases

_$r=3$,4are _{solved in [18]}

andin [5], and forthecase$r=5$, see [5, 28].

Gy\’arf\’as and Lehel discovered abipartite versionofthisconjecture.

Conjecture9 In every r-edge-coloring

_of

a complete bipartite graph, the vertex set

can

be covered by

the vertices

_of

at most$2r-2$ monochromatic connected components.

It is easy to check that any r-edge-coloring of a complete bipartite graph contains at most $2r-1$

monochromatic connectedcomponents coveringthewhole vertex set. Indeed,let $u$and$v$be twovertices

in opposite classes of$K_{m,n}$, and takethe monochromatic double star with centers$u$ and $v$, along with

the remaining monochromatic stars centered at $u$and $v$ (there are at most $2r-2$ suchstars). On the

other hand, it is shown in [4] that there is anr-edge-coloring of a completebipartite graph where we

need at least$2r-2$ monochromatic connectedcomponents tocoverthevertex set.

The recent progress onthis conjectureisthe following:

Theorem 10 ([4]) Conjecture 9 is true

_for

$r\leq 5.$

We now give a quick review concerning the existence oflarge monochromatic trees inedge-colored

graphswith given independencenumber. In [19], Gy\’arf\’asandS\’ark\"ozy investigatedthesizeof

monochro-matictreesinedge-colored graphs.

Theorem 11 ([19]) Any 2-edge-colored graph $G\omega$ntains a monochromatic tree $T$

of

order at least

$|V(G)|/\alpha(G)$.

Theorem 12 ([19]) Any$G$-coloredgraph$G$containsamonochromatic tree$T$

_of

_orderat_least$|V(G)|/(\alpha(G)^{2}+$

$\alpha(G)-1)$.

Theboundon$T$inTheorem 11 is sharp. To

see

this,consider$\alpha(G)$ disjoint monchromaticcomplete

graphs ofequal order. Wedonot know about the best possiblityontheorder of$T$in Theorem 12.

Recently, Theorem 11 was extended toa result on partitioning $V(G)$ by monochromatic connected

Theorem 13 ([8]) Any 2 edge-colored graph $G$ can be partitioned into at most$\alpha(G)$ monochromatic

connected parts.

Now we consider another different covering problem concerning highly connected monochromatic

subgraphs in edge-colored complete graphs. Returningtothecase$r=2$inConjecture 8, weseethat any

2-coloringof$K_{n}$ iscoveredbyamonochromatic connected subgraph. However,whenwetry to find such

asubgraphwith higherconnectivity,we cannot hope tofindsuchaspanningsubgraph. Inorder tosee

this,consider the followingexample:

Let$G_{n}=H_{1}\cup\cdots\cup H_{6}$where$H_{i}$isaredcompletegraph$K_{k-1}$ for$i\leq 4$and$H_{5}$ isa red_{$K_{n}-4(k-1)$}

where $n>4(k-1)$ . To thisstructure, weadd allpossible red edgesbetween $H_{5},$ $H_{1}$ and $H_{2}$ and from

$H_{1}$to $H_{3}$ and from $H_{2}$ to$H_{4}$

.

Alledgesnot already coloredinred arecoloredinblue. Ineither color,

there is no $k$-connected subgraph oforder larger than

$n-2(k-1)$

. Since a spanning monochromatic

subgraph is more thanwe could hope for, we consider finding a highly connected subgraph that is as

largeas possible. Along thisline, Bollob\’asand Gy\’arf\’as [1] proposed the following conjecture.

Conjecture 14 $Forn>4(k-1)$, every 2-coloring

_of

$K_{n}$containsa monochromatic$k$-connected subgraph

withat least$n-2(k-1)$ vertices.

In order to see that thebound on$n$ is the best possible, consider the example$G_{n}$ above with _$n=$

$4(k-1)$ $(so H_{5}=\emptyset)$. In [1], the authorsshowed that this conjectureis true for$k\leq 2.$

Therecent progressconcerning Conjecture14is the following:

Theorem 15 ([14])

_If

$n>6.5(k-1)$ then any 2-edge coloring

of

$K_{n}$ contains a monochromatic

k-connected subgraph

_of

orderat least$n-2(k-1)$

.

By the example $G_{n}$, wemust give up finding a monochromatic $k$-connected subgraphcovering the

vertex set ofa 2edgecolored$K_{n}$

.

But howaboutcovering “almost all theverticesbya monochromatic

$k$-connected subgraph? If$n$ is extremely large compared with $k$, one can say from Theorem 15 that

any 2edge coloring of $K_{n}$ contains a monochromatic $k$-connected subgraph which covers “almost” all

of the vertices. Can we have a similar statement for any r-edge-coloring of$K_{n}$ with $r\geq 3$? This is

not truein general. Ifwe consider an r-edge-coloring of $K_{n}$ and try to find the largest monochromatic

$k$-connectedsubgraphof$K_{n}$,itwasshown in [23] that the bestresultonecouldpossibly hopefor would

bea monochromatic $k$-connected subgraph oforder approximately $\frac{n}{r-1}$

.

Thus, inorder to find larger

monochromatic $k$-connected subgraphs, it becomes necessary to assume additional restrictions on the

coloring.

Finding a monochromatic $k$-connected subgraph covering almost all ofthe vertices corresponds to

finding one color class inducingan “almost” $k$-connectedgraph. In contrast to the concept $DP$ in the

previoussection, oneverynaturalrestrictionwould betoforbid the existenceof a rainbow subgraph.

Thus, wehavethe followingquestion:

Problem 16 Let$n,$$r,$$k$ bepositive integers with_{$n\gg r\gg k$}

.

Forwhat connectedgraphs$G$ _does the

fol-lowingstatement hold9 In any rainbow$G$

-free

coloring

of

$K_{n}$ usingat$lea\mathcal{S}tr$ colors, thereisa

monochro-matic$k$-connected subgraph

of

orderatleast$n-f(G, r, k)$

for

some

function

$f$ not depending on$n.$

Thefollowing resultgives ananswer toward thisquestion:

Theorem 17 ([15]) The set

of

graphs$G$ such that $G$

satisfies

Question 16 is precisely$K_{3},$$P_{4}^{+}$ and $P_{6}$

and theirsubgraphs.

References

[1] B. Bollob\’as, A. Gy\’arf\’as, Highly connected monochromatic subgraphs, Discrete Math., 308 (2008),

[2] K. Cameron, J. Edmonds, Lambdacomposition, J. Graph Theory26 $(1997)_{\rangle}9-16.$

[3] K.Cameron,J. Edmonds, L. Lov\’asz,A note onperfectgraphs,Periodica Math. Hungar., 17(1986),

173-175.

[4] G. Chen, S. Fujita, A. Gy\’arf\’as, J. Lehel,

\’A.

T\’oth, Around a biclique cover $conjecture_{\rangle}$

arXiv:1212.6861 [math. CO].

[5] P. Duchet, Repr\’esentations, noyauxen theorie des graphesat hypergraphes, Thesis, Paris 1979.

[6] R. J. Faudree, L. Lesniak, I. Schiermeyer, On the

_{circumference}

_of

a graph and its complement,

Discrete Math., 309 (2009), 5891-5893.

[7] S. Fujita, Some remarks on long monochromatic cycles in edge-colored complete graphs, Discrete

Math., 311 (2011), 688-689.

[8] S. Fujita,M.Furuya,A. Gy\’arf\’as,

A.

T\’oth, Partition

of

graphsand hypergraphs into monochromatic

connected parts, Electronic J. Combin., 19 (2012),

_#P27.

[9] S. Fujita, A. Gy\’arf\’as, C. Magnant, A. Seress, Disconnected colors in generalized Gallai colorings, J.

Graph Theory, 74 (2013), 104-114.

[10] S.Fujita, L.Lesniak, Revisit

_of

Erd\’os-Gallai’s theorem onthe

_{circumference of}

agraph,Information

ProcessingLetters, 113(2013), 646-648.

[11] S. Fujita, L. Lesniak,

\’A.

T\’oth, Furtherremarks onlongmonochromatic cycles in edge-colored

com-plete graphs,J. Combin. Math. Combin. Comput., In press.

[12] S. Fujita, C.Magnant, Extensions

_of

Gallai-Ramseyresults,J. GraphTheory, 70 (2012), 404-426.

[13] S. Fujita,C. Magnant, GallaiRamseynumbers

_for

cycles,Discrete Math., 311 (2011), 1247-1254.

[14] S. Fujita, C. Magnant, Note on highly connected monochromatic subgraphs in $2-\omega lored$ _complete

graphs, Electronic J. Combin., 18 (2011),

_#P15.

[15] S.Fujita, C. Magnant, Forbidden rainbow subgraphs that

_force

highly connected monochromatic

sub-graphs, SIAMJ. onDiscrete Math., 27 (2013), 1625-1637.

[16] S. Fujita, C. Magnant, K. Ozeki, Rainbow generalizations

_of

ramsey theory: A survey, Graphs and

Combin., 26 (2010), 1-30.

[17] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Sci. Hungar., 18 (1967), 25-66. English

translationin [26].

[18] A. Gy\’arf\’as, Partition coverings and blockingsets in hypergraphs (in Hungarian), Communications

of the ComputerandAutomation Institute ofthe Hungarian AcademyofSciences 71 (1977), 62 pp.

MR58, 5392.

[19] A. Gy\’arf\’as, G. N. S\’ark\"ozy, Gallai colorings

_of

non-complete graphs, Discrete Math., 310 (2010),

977-980.

[20] A. Gy\’arf\’as, G. Simonyi, Edge colorings

_of

complete graphs without tricolored triangles, J. Graph

Theory 46 (2004), 211-216.

[21] A. Gy\’arf\’as, G. N. S\’ark\"ozy, A. Seb\’o, S. Selkow, Ramsey-type results for Gallai colorings, J. Graph

Theory 64 (2009), 233-243.

[22] J. R. Henderson, Permutation decomposition

of

(0–1)-matrices and decomposition $tran\mathcal{S}$versals,

[23] H. Liu, R. Morris,N. Prince, Highly connected monochromatic subgraphs

_of

multicoloredgraphs, J.

GraphTheory 61 (2009), 22-44.

[24] J. $K\ddot{\circ}$rner, G. Simonyi, Graph pairs and their entropies: Modularity problems, Combinatorica 20

(2000), 227-240.

[25] J. K\"orner, G. Simonyi, Z. Tuza,

_Perfect

couples

_of

graphs,Combinatorica 12 (1992), 179-192.

[26] F.$Maffray_{\rangle}$ M. Preissmann, A Translation

of

Gallai’sPaper: TVansitiv orientierbare Graphen, in:J.

L. Ramirez-Alfonsin andB.A. Reed (editors), Perfect Graphs, John Wiley andSons, (2001), 25-66.

[27] J. Lehel, Ryser’sconjecture

_for

linear hypergraphs, manuscript, 1998.