The lexicographic method for the threshold cover problem

Contents lists available atScienceDirect

Discrete Mathematics

journalhomepage:www.elsevier.com/locate/disc

The lexicographic method for the threshold cover problem ^✩

Mathew C. Francis

^a

, Dalu Jacob

^b

^,

^∗

aIndianStatisticalInstitute,ChennaiCentre,India bIndianInstituteofScience,Bangalore,India

a rt i c l e i nf o a b s t ra c t

Articlehistory:

Received14March2022

Receivedinrevisedform28January2023 Accepted31January2023

Availableonlinexxxx

Keywords:

Thresholdcover Chainsubgraphcover Lexicographicmethod

Threshold graphs are aclassofgraphs that have manyequivalentdefinitions and have applications ininteger programmingand set packingproblems. Agraphis saidto have athresholdcoverofsizekifitsedgescanbecoveredusingkthreshold graphs.Chvátal andHammer,in1977,definedthethresholddimensionth(G)ofagraphGtobetheleast integerksuchthat G hasathresholdcoverofsizekand observedthat th(G)≥

χ

(G^∗), where G^∗isasuitablyconstructedauxiliarygraph.Raschleand Simon(1995)[9] proved thatth(G)=

χ

(G^∗)wheneverG^∗isbipartite.Weshowhowthelexicographicmethodof Hell andHuang canbeused toobtainacompletelynewand, webelieve,simplerproof for thisresult.Forthe case whenG is asplitgraph,our methodyieldsaproof that is much shorterthanthe onesknowninthe literature.Ourmethods giveriseto asimple and straightforward algorithmtogeneratea2-threshold coverofaninput graph,ifone exists.

©^{2023ElsevierB.V.Allrightsreserved.}

1. Introduction

We consideronly simple,undirectedand finitegraphs.We denote an edgebetweentwo vertices u and v ofa graph bythetwo-element set

{

^u

,

v

}

^{,whichisusually}abbreviatedtojustuv.Twoedgesab

,

cdinagraphG aresaid toforman alternating4-cycle ifad

,

bc

∈

^E

(

G

)

. Agraph G that doesnot containanypair ofedges that forman alternating 4-cycleis calledathresholdgraph;orequivalently,G is

(

2K₂

,

P₄

,

C₄

)

-free [1].AgraphG

= (

V

,

E

)

issaidtobe coveredbythegraphs H₁

,

H₂

, . . . ,

H_kifE

(

G

) =

^E

(

H₁

) ∪

^E

(

H₂

) ∪ · · · ∪

^E

(

H_k

)

.

Definition1(Thresholdcoverandthresholddimension).AgraphGissaidtohaveathresholdcoverofsizekifitcanbecovered bykthresholdgraphs.ThethresholddimensionofagraphG,denotedasth

(

G

)

,isdefinedtobethesmallestintegerksuch that Ghasathresholdcoverofsizek.

MahadevandPeled [8] giveacomprehensivesurveyofthresholdgraphsandtheirapplications.

Chvátal andHammer [1] showed thatthefact thata graphG hasth

(

G

) ≤

^{k isequivalent tothefollowing:there exist} klinearinequalitieson

|

^V

(

G

) |

^{variablessuchthatthe}characteristicvectorofaset S

⊆

^V

(

G

)

satisfiesalltheinequalitiesif

✩ Apreliminaryversionofthispaper,claimingthesameresultasprovedinthiswork,appearedintheproceedingsoftheconferenceCALDAM2020.But theproofinthatversioncontainsaseriouserror,andthealgorithmmentionedinthatpapermayfailtoproducea2-thresholdcoveriftheinputgraph containsaparagliderasaninducedsubgraph.

*

Correspondingauthor.

E-mailaddresses:mathew@isichennai.res.in(M.C. Francis),dalu1991@gmail.com(D. Jacob).

https://doi.org/10.1016/j.disc.2023.113364 0012-365X/©^{2023ElsevierB.V.Allrightsreserved.}

a

f g

b c

d e

ab ac

f g bf

c f e f

cg

dg bc

bd

be

cd de

(a) (b)

Fig. 1.(a) A graphG, and (b) the auxiliary graphG^∗ofG.

andonlyifS isanindependentsetofG(see [9] fordetails).TheyfurtherdefinedtheauxiliarygraphG^∗corresponding to agraphGasfollows.

Definition 2 (Auxiliarygraph).Given a graph G, the graph G^∗ has vertex set V

(

G^∗

) =

^E

(

G

)

and edge set E

(

G^∗

) = {{

^ab

,

cd

}:

^ab

,

cd

∈

^E

(

G

)

suchthatab

,

cdformanalternating4-cycleinG

}

^.

AgraphG andtheauxiliary graphG^∗ correspondingtoitisshowninFig.1.ChvátalandHammerobservedthatsince foranysubgraph HofG thatisathresholdgraph, E

(

H

)

isanindependentsetinG^∗,thefollowinglowerboundonth

(

G

)

holds.

Lemma1(Chvátal-Hammer).th

(

G

) ≥ χ (

G^∗

)

.

This gave rise to the question of whetherthere is anygraph G such that th

(

G

) > χ (

G^∗

)

.Cozzens and Leibowitz [4]

showed the existence of such graphs. In particular, they showedthat forevery k

≥

^{4, there exists a graph G such that}

χ (

G^∗

) =

^{k butth}

(

G

) >

k.Whilethequestion ofwhethersuchgraphsexistfork

=

^{3 doesnotseemtohavereceivedmuch} attentionandstillremainsopen(tothebestofourknowledge),thequestionforthecasek

=

^{2 wasstudiedquite}intensively (see [7]).IbarakiandPeled [6] showed,by meansofsomeveryinvolvedproofs,thatifG isasplitgraphorifG^∗ contains atmosttwo non-trivialcomponents,then

χ (

G^∗

) =

^{2 ifandonlyifth}

(

G

) =

^{2.Theyfurther}conjecturedthat foranygraph G,

χ (

G^∗

) =

²

⇔

^th

(

G

) =

^{2.Iftheconjectureheld,itwouldshow}immediatelythat graphshavingathresholdcoverofsize 2can berecognized inpolynomialtime,since theauxiliarygraph G^∗ canbe constructedanditsbipartitenesscheckedin polynomial time.Incontrast,Yannakakis [12] showed thatitisNP-completetorecognize graphshavingathresholdcover ofsize3.CozzensandHalsey [3] studiedsome propertiesofgraphshavingathresholdcoverofsize 2andshowedthatit can bedecided inpolynomial time whetherthecomplementofabipartite graphhasa thresholdcoverofsize 2.Finally, morethanadecadeafterthequestionwasfirstposed,RaschleandSimon [9] provedtheconjectureofIbarakiandPeledby extendingthemethodsin [6].

Theorem1(Raschle-Simon).ForanygraphG,

χ (

G^∗

) =

^{2ifandonlyifth}

(

G

) =

^2.

This proof of Raschle andSimon is very technical and involves the use of a numberof complicated reductions and previouslyknownresults.Inthispaper,weprovideanew,andwebelieve,simpler,proofforTheorem1.

Weconstructanalgorithmthatgeneratesa2-thresholdcoverofaninputgraphGifG^∗isbipartite.InSections3and4, wedescribethealgorithmanditsproofofcorrectnessforthecasewhentheinputgraphbelongstotheclassof“paraglider- free” graphs,which isa superclassofthe classof chordalgraphs. Sinceall splitgraphs are alsochordal graphs,we have a proof ofTheorem 1for thecaseofsplit graphs inSection 4itself. We believe thatthis prooffor splitgraphs ismuch simplerandshorterthantheproofforsplitgraphsgivenbyIbarakiandPeled [6] (ortheproofofRaschleandSimon [9] for generalgraphsthatbuildsupontheworkofIbarakiandPeled).InSection 5,weshowhowouralgorithmcanbemodified toworkforgeneralgraphs.Notethatforthecaseofgeneralgraphs,eventhoughthealgorithmremains simple,theproof ofitscorrectnessbecomesmoreinvolved.

Outlineofthealgorithm.LetG beanygraphsuchthatG^∗isbipartite.Wewouldliketoconstructathresholdcoverofsize 2forG.Anaturalwaytoapproachtheproblemistocomputea2-coloringofG^∗,whichcorrespondstoapartitionofthe edgesetofG intotwosets,sayE1andE2,andtrytoshowthatG1

= (

V

(

G

),

E1

)

andG2

= (

V

(

G

),

E2

)

arethresholdgraphs (and so

{

^G1

,

G2

}

^{is a} 2-thresholdcover of G). But thisapproach doesnot work since if we take an arbitrary 2-coloring of G^∗,the graphs G₁ and G₂ need not necessarilybe thresholdgraphs (thiscan be easily seenin thecasewhen G isa completegraph,asthenG^∗ containsonlyisolatedvertices).Instead,ouralgorithmgeneratesaspecialkindof2-coloringof

G^∗,whichisthenusedtoconstructa2-thresholdcoverofG.LetX denotethesetofisolatedverticesinG^∗.Ouralgorithm computesasetY

⊆

^{X anda2-coloringofG∗}

−

^{Y (wecallthisa“partial}2-coloring”ofG^∗)whichpartitionsE

(

G

) \

^{Y into} twosets E1 andE2 such thatthegraphsG1

= (

V

(

G

),

E1

∪

^Y

)

andG2

= (

V

(

G

),

E2

∪

^Y

)

areboththresholdgraphs,thereby yielding a 2-thresholdcover of G. Note that as G^∗ need not be connected, even if X

= ∅

^{,there can be an} exponential numberof2-coloringsofG^∗ andasnotedabove,notevery2-coloringgivesrisetoa2-thresholdcoverofG.Thealgorithm runsintime O

(|

^V

(

G^∗

)| + |

^E

(

G^∗

)|) =

^O

(|

^E

(

G

)|

²

)

.Inthecaseofsplitgraphs,andmoregenerallyparaglider-freegraphs,our algorithmdoesnotneedtoprocesstheisolatedverticesinG^∗ atall;insteaditjusttakesY

=

^{X.Inotherwords,itcomputes} a 2-coloringofG^∗

−

^{X whichpartitions E}

(

G

) \

^{X intotwo sets E}1 andE2 such thatthegraphs G1

= (

V

(

G

),

E1

∪

^X

)

and G2

= (

V

(

G

),

E2

∪

^X

)

areboththresholdgraphs.

TheChainSubgraphCoverProblem. Abipartite graph G

= (

A

,

B

,

E

)

is calleda chaingraph if itdoes not contain a pair ofedges whose endpointsinduce a2K2 in G.LetG

ˆ

be thesplitgraph obtainedfromG byaddingedges betweenevery pair ofverticesin A (or B). Itcan be seenthat G isa chaingraph ifandonlyif G

ˆ

isa thresholdgraph.A collectionof chaingraphs

{

H1

,

H2

, . . . ,

Hk

}

issaidtobeak-chainsubgraphcoverofabipartitegraphG ifitiscoveredby H1

,

H2

, . . . ,

Hk. Yannakakis [12] creditsMartinGolumbicforobservingthat a bipartitegraph G hasa k-chainsubgraph coverifandonly ifG

ˆ

hasak-thresholdcover.The problemofdecidingwhetherabipartite graphG can becovered byk chaingraphs,i.e.

whetherG hasak-chainsubgraphcover,isknownasthek-chainsubgraphcover(k-CSC)problem. Yannakakis [12] showed that 3-CSC isNP-complete, whichimplies that theproblem ofdeciding whether th

(

G

) ≤

^{3 for an input graph G is also} NP-complete. He also pointedout that using Golumbic’s observationand theresults of Ibarakiand Peled [6], the 2-CSC problemcanbesolved inpolynomial time,asitcan bereducedto theproblemofdeterminingwhethera splitgraphcan be coveredbytwothresholdgraphs.Thusouralgorithmforsplitgraphscanalsobe usedtocomputea2-chainsubgraph cover,ifoneexists,foran inputbipartitegraph Gintime O

( |

^E

(

G

) |

²

)

(notethateventhough

|

^E

(

G

ˆ ) | > |

^E

(

G

) |

^,thevertices inG

ˆ

^∗ correspondingtotheedgesin E

(

G

ˆ ) \

^E

(

G

)

areallisolatedverticesandhencedonot needtobeputinG^∗ sinceour algorithmforsplitgraphsdoesnottakethemintoaccountanyway).NotethatMaandSpinrad [7] proposeamoreinvolved O

( |

^V

(

G

) |

²

)

algorithmfortheproblem. However,ouralgorithm forsplit graphs,andhencethealgorithm forcomputinga 2-chainsubgraphcoverthatityields,isconsiderablysimplertoimplementthanthealgorithmsof [6,7,9,11].

Lex-BFSorderings.ALex-BFSorderingofagraphisan orderingoftheverticesofthegraphhavingthepropertythat itis possibleforaLexicographicBreadthFirstSearch(Lex-BFS)algorithmtovisittheverticesofthegraphinthatorder.ALex-BFS orderingisalsoaBFSordering—i.e.,abreadth-firstsearchalgorithmcanalsovisittheverticesinthatorder—butithassome additionalproperties.Lex-BFScanbeimplementedtorunintimelinearinthesizeoftheinputgraphandwasintroduced by Rose, TarjanandLueker [10] toconstructa linear-time algorithmforrecognizing chordalgraphs. Later,Lex-BFSbased algorithmswerediscoveredfortherecognitionofmanydifferentgraphclasses(see [2] forasurvey).

TheLexicographicMethod. We use a technique calledthe lexicographicmethod introduced by Hell and Huang [5], who demonstrated how thismethod can lead to shorter proofsand simplerrecognition algorithms forcertain problems that involveconstructingaspecific2-coloringofanauxiliarybipartitegraphthatcapturescertainrelationshipsamongtheedges ofthegraph.Themethodinvolvesfixinganordering

<

oftheverticesofthegraph,andthenprocessingtheedges inthe

“lexicographicorder”impliedbytheordering

<

.Weadaptthistechniquetoconstructapartial2-coloringofG^∗thatcanbe usedtogeneratea2-thresholdcoverofG.Hell andHuang [5] startwithanarbitraryorderingoftheverticesofthegraph intheirrecognitionalgorithms forcomparability graphsandpropercircular-arcgraphs,butforthecaseofproperinterval graphs,theystartwitha“perfecteliminationordering”ofthegivengraph,whichshouldnecessarilyexistwhenthegraphis chordal(notethatproperintervalgraphsformasubclassofchordalgraphs).FromtheworkofRose,TarjanandLueker [10], it isknown that forchordal graphs, theperfectelimination orderings are exactlythe reversalsof Lex-BFSorderings.Thus therecognitionalgorithmforproperintervalgraphsbasedonthelexicographicmethodthatisgivenin [5] startswiththe reversalofaLex-BFSorderingoftheinputgraph.Asweshallsee,ourrecognitionalgorithmforgraphshavinga2-threshold coverstarts witha Lex-BFSorderof theinput graph.Whenit isknownthat theinput graphisa “paraglider-freegraph”

(definedinSection4),wecanevenstartwithanarbitraryorderingoftheverticesoftheinputgraph.

2. Preliminaries

LetG

= (

V

,

E

)

beanygraph.Recallthatedgesab

,

cd

∈

^E

(

G

)

formanalternating4-cycleifbc

,

da

∈

^E

(

G

)

.Inthiscase,we alsosaythata

,

b

,

c

,

d

,

a isanalternating4-cycleinG (alternating4-cyclesarecalled AC4sin [9]).Theedgesabandcdare saidto betheoppositeedgesofthealternating 4-cyclea

,

b

,

c

,

d

,

a.Thusforagraph G,theauxiliary graphG^∗ isthegraph withV

(

G^∗

) =

^E

(

G

)

andE

(

G^∗

) = {{

^ab

,

cd

}:

^ab

,

cd

∈

^E

(

G

)

aretheoppositeedgesofanalternating4-cycleinG

}

^.Notethatit followsfromthedefinitionof analternating 4-cycle thatifa

,

b

,

c

,

d

,

a isan alternating 4-cycle,then theverticesa

,

b

,

c

,

d are pairwise distinct.We shallrefer tothevertexof G^∗ corresponding to anedge ab

∈

^E

(

G

)

alternativelyas

{

^a

,

b

}

^orab, dependinguponthecontext.

OurgoalistoprovideanewproofforTheorem1.

a

b e

c d

(a)

a

b c

d

(b)

a

b c

d

(c)

Fig. 2.(a)AnA1-pentagon,(b)anA1-switchingpath,and(c)anA1-switchingcycle.Ineachofthefigures:adashedlinebetweentwoverticesindicates thattheyarenon-adjacent,athinlinerepresentsanedgethatmaybeineitherA1orA0,athicklineindicatesanedgeinA1,andagraylinerepresents anedgeinA2.

It is easy to see that

χ (

G^∗

) =

^{1 if and only if th}

(

G

) =

^{1. Therefore, by Lemma 1, it is enough to prove that if G∗} is bipartite, then G can be coveredby two threshold graphs.In order toprove this, we find a specific 2-coloringof the non-trivialcomponentsofG^∗ (componentsofsizeatleast2)usingthelexicographicmethodofHellandHuang [5].

We saythat

(

A0

,

A1

,

A2

)

is avalid3-partitionof E

(

G

)

if

{

^A0

,

A1

,

A2

}

^{isa partition of E}

(

G

)

with theproperty that in anyalternating 4-cycle inG, oneofthe oppositeedges belongsto A₁ andtheother to A₂.Inother words, foranyedge

{

^ab

,

cd

} ∈

^E

(

G^∗

)

,oneofab

,

cdisin A1andtheotherin A2.Notethatthismeanswhilesomeedgesin A1andA2 mayhave thepropertythattheydonotformanalternating4-cyclewithanyotheredge,everyedgeinA0definitelyhasthisproperty.

Givena valid3-partition

(

A0

,

A1

,

A2

)

of E

(

G

)

and A

∈ {

^A1

,

A2

}

^{,we saythat a}

,

b

,

c

,

d isan alternatingA-path ifa

=

^d, ab

,

cd

∈

^A

∪

^A0,andbc

∈

^E

(

G

)

.Further,we saythata

,

b

,

c

,

d

,

e

,

f

,

a isan alternatingA-circuit ifa

=

^d,ab

,

cd

,

e f

∈

^A

∪

^A0, andbc

,

de

,

f a

∈

^E

(

G

)

.

Observation1.Let

(

A₀

,

A₁

,

A₂

)

beavalid3-partitionofE

(

G

)

andlet

{

^A

,

A

} = {

^A1

,

A₂

}

^. (a) Ifa

,

b

,

c

,

d isanalternatingA-path,thenad

∈

^E

(

G

)

.

(b) Ifa

,

b

,

c

,

d

,

e

,

f

,

a isanalternatingA-circuit,thene f

∈

^{A andad}

∈

^A.

Proof. Toprove (a), itjust needs to beobserved that ifad

∈

^E

(

G

)

,then a

,

b

,

c

,

d

,

a would bean alternating 4-cycle in G whoseoppositeedgesbothbelongto A

∪

^A0,whichcontradictsthefactthat

(

A0

,

A1

,

A2

)

isavalid3-partitionof E

(

G

)

.To prove (b),suppose thata

,

b

,

c

,

d

,

e

,

f

,

a isanalternating A-circuit.Sincea

,

b

,

c

,

dis analternating A-path,we haveby (a) thatad

∈

^E

(

G

)

.Thensincea

,

d

,

e

,

f

,

aisanalternating4-cycleinGande f

∈

^A

∪

^A0,itfollowsthate f

∈

^{A andad}

∈

^A.

Weshallusetheaboveobservationthroughoutthispaperwithoutreferringtoitexplicitly.

Let

(

A0

,

A1

,

A2

)

beavalid3-partitionofE

(

G

)

andlet

{

^A

,

A

} = {

^A1

,

A2

}

^.Wesaythat

(

a

,

b

,

c

,

d

,

e

)

isan A-pentagoninG withrespectto

(

A₀

,

A₁

,

A₂

)

ifa

,

b

,

c

,

d

,

e

∈

^V

(

G

)

,ac

,

ad

,

be

∈

^E

(

G

)

,ab

,

ae

∈

^A,bc

,

bd

,

ec

,

ed

∈

^Aandcd

∈

^A

∪

^A0.Weabbreviate thistojust“A-pentagon”whenthegraphG andthe3-partition

(

A0

,

A1

,

A2

)

ofGare clearfromthecontext.Wesaythat an A-pentagon

(

a

,

b

,

c

,

d

,

e

)

isastrictA-pentagonifcd

∈

^A.Wesaythat

(

a

,

b

,

c

,

d

,

e

)

isapentagon(resp.strictpentagon)ifit isan A-pentagon(resp.strict A-pentagon)forsome A

∈ {

^A1

,

A2

}

^{.(Pentagonsaresimilartothe“A P}5-s”in [9].)

Wesaythat

(

a

,

b

,

c

,

d

)

isan A-switchingpathinG withrespectto

(

A₀

,

A₁

,

A₂

)

ifa

,

b

,

c

,

d

∈

^V

(

G

)

,ad

∈

^E

(

G

)

,ab

,

cd

∈

^A

∪

^A0, and bc

∈

^{A. When the graph G andthe} 3-partition

(

A0

,

A1

,

A2

)

of G are clear from the context, we abbreviate this to just “A-switching path”. We say that

(

a

,

b

,

c

,

d

)

is a strict A-switchingpath ifit is an A-switching path and in addition, ab

,

cd

∈

^{A. We say that}

(

a

,

b

,

c

,

d

)

is a switchingpath (resp. strictswitchingpath) ifit is an A-switching path (resp.strict A-switchingpath)forsome A

∈ {

^A1

,

A₂

}

^.Wesaythat

(

a

,

b

,

c

,

d

)

isan A-switchingcycleinG withrespectto

(

A₀

,

A₁

,

A₂

)

if ab

,

cd

∈

^A

∪

^A0andbc

,

ad

∈

^{A.Asbefore,wesaythat}

(

a

,

b

,

c

,

d

)

isaswitchingcycleinGwithrespectto

(

A₀

,

A₁

,

A₂

)

ifthere exists A

∈ {

^A1

,

A2

}

^suchthat

(

a

,

b

,

c

,

d

)

isan A-switchingcycle.

Note that from thedefinitions of pentagons,switching paths and switchingcycles, it followsthat if

(

a

,

b

,

c

,

d

,

e

)

isa pentagon,thentheverticesa

,

b

,

c

,

d

,

earepairwisedistinct,andif

(

a

,

b

,

c

,

d

)

isaswitchingpathoraswitchingcycle,then the vertices a

,

b

,

c

,

d are pairwise distinct. Fig. 2 illustrates an A₁-pentagon, an A₁-switchingpath, andan A₁-switching cycle.

Lemma2.Let

(

A₀

,

A₁

,

A₂

)

beavalid3-partitionofE

(

G

)

.IftherearenoswitchingpathsandnoswitchingcyclesinG withrespectto

(

A0

,

A1

,

A2

)

thenth

(

G

) =

^2.

Proof. Considerthegraphs H₁

,

H₂,having V

(

H₁

) =

^V

(

H₂

) =

^V

(

G

)

,E

(

H₁

) =

^A1

∪

^A0 andE

(

H₂

) =

^A2

∪

^A0.Weclaimthat H1 and H2 are both threshold graphs. Suppose forthe sake of contradictionthat Hi isnot a threshold graph forsome

i

∈ {

¹

,

2

}

^{.Thenthereexistedgesab}

,

cd

∈

^E

(

Hi

)

suchthatbc

,

ad

∈

^E

(

Hi

)

.Ifbc

,

ad

∈

^E

(

G

)

,thena

,

b

,

c

,

d

,

aisanalternating4- cycleinGwhoseoppositeedgesbothbelongtoA_i

∪

^A0,whichcontradictsthefactthat

(

A₀

,

A₁

,

A₂

)

isavalid3-partition.So wecanassumebysymmetrythatbc

∈

^E

(

G

)

.Sincebc

∈

^E

(

Hi

)

,bc

∈ /

^Ai

∪

^A0,whichimpliesthatbc

∈

^A3−ⁱ.Nowifad

∈

^E

(

G

)

, then

(

a

,

b

,

c

,

d

)

isan Ai-switchingpath inG withrespectto

(

A0

,

A1

,

A2

)

,which isacontradiction. Ontheother hand,if ad

∈

^E

(

G

)

, thenad

∈

^A3−ⁱ (sincead

∈

^E

(

H_i

)

), whichimpliesthat

(

a

,

b

,

c

,

d

)

is an A_i-switchingcyclein G withrespect to

(

A0

,

A1

,

A2

)

,whichisagainacontradiction.Thuswecanconcludethatboth H1 andH2arethresholdgraphs.

Lemma3.Let

(

A₀

,

A₁

,

A₂

)

beavalid3-partitionofE

(

G

)

.Let

{

^A

,

A

} = {

^A1

,

A₂

}

^.Let

(

x

,

y

,

z

,

w

)

beanA-switchingpathinG andlet yz

∈

^E

(

G

)

besuchthatyz

,

zy

∈

^E

(

G

)

.Then,

(a) ifx

=

^y,then

(

x

=

^y

,

y

,

z

,

w

,

z

)

isanA-pentagonand (b) ifw

=

^z,then

(

w

=

^z

,

z

,

y

,

x

,

y

)

isanA-pentagon.

Proof. Since yz

∈

^Aand

{

^yz

,

yz

} ∈

^E

(

G^∗

)

wehavethat yz

∈

^{A.Supposethat x}

=

^{y.Then y}

, (

x

=

^y

),

z

,

w

, (

x

=

^y

),

z

,

y isan alternating A-circuit (notethat y

=

^{w asx}

∈

^N

(

y

) \

^N

(

w

)

),implying that y w

∈

^{A.Thisfurtherimpliesthat z}

=

^w.

Then we also havealternating A-circuits z

,

y

,

z

,

w

,

x

,

y

,

z and z

, (

y

=

^x

),

w

,

z

, (

y

=

^x

),

y

,

z,implying that xy

∈

^{A and} zw

,

zz

∈

^A. Consequently,

(

x

=

^y

,

y

,

z

,

w

,

z

)

is an A-pentagon. Since

(

w

,

z

,

y

,

x

)

is also an A-switching path, we can similarlyconcludethatifw

=

^z,then

(

w

=

^z

,

z

,

y

,

x

,

y

)

isan A-pentagon.

Wethenhavethefollowingcorollary.

Corollary1.Let

(

A₀

,

A₁

,

A₂

)

beavalid3-partitionofE

(

G

)

.Supposethattherearenopentagons(resp.strictpentagons)inG with respectto

(

A0

,

A1

,

A2

)

.Let

(

x

,

y

,

z

,

w

)

beaswitchingpath(resp.strictswitchingpath)withrespectto

(

A0

,

A1

,

A2

)

.Letyz

∈

^E

(

G

)

besuchthatyz

,

zy

∈

^E

(

G

)

.Then,y

=

^{x andz}

=

^w.

Proof. Let

{

^A

,

A

} = {

^A1

,

A2

}

^{.Supposethattherearenopentagons(resp.strictpentagons)inGwithrespectto}

(

A0

,

A1

,

A2

)

. Let

(

x

,

y

,

z

,

w

)

bean A-switchingpath (resp.strict A-switchingpath, andtherefore xy

,

zw

∈

^{A). ByLemma 3, we know} that if y

=

^{x then}

(

x

=

^y

,

y

,

z

,

w

,

z

)

isan A-pentagon (resp.a strict A-pentagon, as zw

∈

^{A), andifz}

=

^{w then}

(

w

=

z

,

z

,

y

,

x

,

y

)

isan A-pentagon (resp.astrict A-pentagon,asxy

∈

^{A).Sincetherearenopentagons(resp.strict}pentagons), wecanconcludethat y

=

^xandz

=

^w.

Let

<

be an ordering of the verticesof G. Giventwo k-element subsets S

= {

^s1

,

s2

, . . . ,

s_k

}

^{and T}

= {

^t1

,

t2

, . . . ,

t_k

}

^of V

(

G

)

,wheres1

<

s2

< · · · <

sk andt1

<

t2

< · · · <

tk, S issaidtobe lexicographicallysmallerthan T,denotedby S

<

T,if s_j

<

t_jforsome j

∈ {

¹

,

2

, . . . ,

k

}

^,andsi

=

^tiforall1

≤

ⁱ

<

j.Intheusualway,weletS

≤

^{T denotethefactthateitherS}

<

T or S

=

^{T.Foraset S}

⊆

^V

(

G

)

,we abbreviatemin_<S tojust minS.Notethat therelation

<

(“is lexicographically smaller than”)thatwehavedefinedonk-elementsubsetsofV

(

G

)

isatotalorder.Therefore,givenacollectionofk-elementsubsets ofV

(

G

)

,thelexicographicallysmallestoneamongthemiswell-defined.

Thefollowingobservationstatesawell-knownpropertyofLex-BFSorderings [2].

Observation2.Let

<

denoteaLex-BFSorderingofagraphG.Fora

,

b

,

c

∈

^V

(

G

)

,ifa

<

b

<

c,ab

∈ /

^E

(

G

)

andac

∈

^E

(

G

)

,thenthere existsx

∈

^V

(

G

)

suchthatx

<

a

<

b

<

c,xb

∈

^E

(

G

)

andxc

∈ /

^E

(

G

)

.

3. Thealgorithm

Let G be a graph such that G^∗ is bipartite. For two vertices ab

,

ab

∈

^V

(

G^∗

)

(i.e. ab

,

ab

∈

^E

(

G

)

), we say that ab is lexicographicallysmallerthanab withrespecttoanordering

<

ofV

(

G

)

,if

{

^a

,

b

} < {

^a

,

b

}

^.

Weshallnowconstructa partial2-coloringoftheverticesofG^∗ usingthecolors

{

¹

,

2

}

^{bymeansofanalgorithm,and} thenconstructavalid3-partitionofE

(

G

)

usingthispartial2-coloring.

PhaseI.ConstructaLex-BFSordering

<

ofG.

RecallthateveryvertexofG^∗ isatwo-elementsubsetofV

(

G

)

.

Phase II.For every non-trivial componentC ofG^∗, perform the following operation:

Choose the lexicographically smallest vertex inC (with respect to the ordering

<

) and assign the color 1 to it. Extend this to a proper coloring ofCusing the colors

{

¹

,

2

}

^.

Note that after Phase II, every vertex of G^∗ that is in a non-trivial component has been colored either 1 or 2. For i

∈ {

¹

,

2

}

^{,let F}i

= {

^e

∈

^V

(

G^∗

) :

^{eis coloredi}

}

^{.Further,let F}0 denotethesetofall isolated vertices(trivialcomponents) in

G^∗.Clearly,F0isexactlythesetofuncoloredverticesofG^∗andwehaveV

(

G^∗

) =

^F0

∪

^F1

∪

^F2.Notethatsincetheopposite edgesofanyalternating4-cycleinGcorrespondtoadjacentverticesinG^∗,oneofthemreceivescolor1andtheothercolor 2inthepartial2-coloringofG^∗ constructedinPhaseII.Itfollowsthat

(

F0

,

F1

,

F2

)

isavalid3-partitionofE

(

G

)

.

Firstwenotethefollowinglemma.

Lemma4.IftherearenostrictpentagonsinG withrespectto

(

F0

,

F1

,

F2

)

,thentherearenostrictswitchingpathsinG withrespect to

(

F0

,

F1

,

F2

)

.

Proof. Supposethat G contains a strictswitchingpath.We saythata strictswitchingpath

(

a

,

b

,

c

,

d

)

islexicographically smallerthanastrictswitchingpath

(

a

,

b

,

c

,

d

)

if

{

^a

,

b

,

c

,

d

} < {

^a

,

b

,

c

,

d

}

^.Let

(

a

,

b

,

c

,

d

)

bethelexicographicallysmallest strictswitchingpathinG.

Claim.

(

a

,

b

,

c

,

d

)

isnotastrictF1-switchingpath.

Supposeforthesake ofcontradictionthat

(

a

,

b

,

c

,

d

)

isastrict F1-switchingpath.LetC be thecomponentof G^∗ con- tainingbc.Letb0c0

,

b1c1

, . . . ,

bkck,whereb0

=

^bandc0

=

^{c,beapathinC betweenbcandthe}lexicographicallysmallest vertexb_kc_kin C.Weassume thatforeachi

∈ {

⁰

,

1

, . . . ,

k

−

¹

}

^,bic_i+1

,

c_ib_i+1

∈

^E

(

G

)

.Asb₀c₀

∈

^F2,itfollowsthatb_ic_i

∈

^F2 foreacheveni andb_ic_i

∈

^F1 foreach oddi.Sinceb_kc_kisthelexicographicallysmallestvertexinitscomponentinG^∗,we knowthatbkck

∈

^F1,whichimpliesthatkisodd.

Weclaimthatbia

,

cid

∈

^F1 foreacheveni andbia

,

cid

∈

^F2 foreachoddi,where0

≤

ⁱ

≤

^{k.Weprovethisbyinduction} on i. The case where i

=

^{0 is trivial as b}0

=

^{b and c}0

=

^{c. So let us assume that i}

>

0. Consider the case where i is odd. As i

−

^{1 iseven, by the inductionhypothesis we have b}i−¹a

,

ci−¹d

∈

^F1. Since bi−¹ci−¹

∈

^F2, we can observethat,

(

a

,

bi−¹

,

ci−¹

,

d

)

isastrict F1-switchingpath.ThenbyCorollary1,we havethata

=

^bi andd

=

^ci.Now thealternating F1- circuits b_i

,

c_i

,

b_i−1

,

a

,

d

,

c_i−1

,

b_i andc_i

,

b_i

,

c_i−1

,

d

,

a

,

b_i−1

,

c_i implythat b_ia

,

c_id

∈

^F2.Thecasewherei iseven issymmetric andhencetheclaim.

By the above claim,bka

,

ckd

∈

^F2. Since bkck

∈

^F1, we now havethat

(

a

,

bk

,

ck

,

d

)

is a strict F2-switching path.Since bkck

<

bc,wehavethat

{

a

,

bk

,

ck

,

d

} < {

a

,

b

,

c

,

d

}

,which isacontradictiontoour assumptionthat

(

a

,

b

,

c

,

d

)

isthelexico- graphicallysmalleststrictswitchingpathinG.Thisprovestheclaim.

Bythe aboveclaim, we havethat

(

a

,

b

,

c

,

d

)

is astrict F2-switchingpath.By thesymmetry betweena andd, wecan assumewithoutlossofgeneralitythata

<

d.

As bc

∈

^F1,thevertexbc belongstoanon-trivialcomponentofG^∗.Thenthereexists aneighbor uv ofbc inG^∗ such thatbv

,

uc

∈

^E

(

G

)

.Asbc

∈

^F1,wehaveuv

∈

^F2.ByCorollary1,wehavethat u

=

^{a.Then a}

,

b

,

v

,

u

,

c

,

d

,

aisanalternating F₂-circuit,implyingthatau

∈

^F1.Asab

∈

^F2,weknowthatabisnotthelexicographicallysmallestvertexinitscomponent.

Leta0b0

,

a1b1

, . . . ,

a_kb_kbeapathinG^∗betweenabandthelexicographicallysmallestvertexa_kb_k initscomponent,where a0

=

^a,b0

=

^b,andfor0

≤

ⁱ

<

k,aibi+¹

,

ai+¹bi

∈

^E

(

G

)

.Notethatfor0

≤

ⁱ

≤

^k,aibi

∈

^F2 ifiisevenandaibi

∈

^F1 ifi isodd.

Sincea_kb_k

∈

^F1 (asitisthelexicographicallysmallestvertexinitscomponentinG^∗),thisimpliesthatkisodd.

Weclaimthatfor0

≤

ⁱ

≤

^k,aiu

,

b_ic

∈

^F1ifiisevenanda_iu

,

b_ic

∈

^F2ifiisodd.Weprovethisbyinductiononi.Thebase casewheni

=

^{0 istrivial, sinceau}

,

bc

∈

^F1.Leti

>

0 beodd.Bytheinductionhypothesis wehavethat ai−¹u

,

bi−¹c

∈

^F1. Sinceai−¹bi−¹

∈

^F2wecanobservethat

(

u

,

ai−¹

,

bi−¹

,

c

)

isastrict F1-switchingpath.ThereforebyCorollary1,wehavethat a_i

=

^{u andb}i

=

^{c.Then we have} alternating F₁-circuitsa_i

,

b_i

,

a_i−1

,

u

,

c

,

b_i−1

,

a_i andb_i

,

a_i

,

b_i−1

,

c

,

u

,

a_i−1

,

b_i, implyingthat aiu

,

bic

∈

^F2.Thecasewheni isevenissymmetric.Thisprovesourclaim.Sincekisodd,we nowhavethata_ku

,

b_kc

∈

^F2. Notethatnow

(

c

,

bk

,

ak

,

u

)

isastrict F2-switchingpath.

Suppose that d

<

b.Then we havethat a

<

d

<

b, wheread

∈

^E

(

G

)

andab

∈

^E

(

G

)

. Thereforeby Observation 2, there exists x

<

a suchthat xd

∈

^E

(

G

)

andxb

∈

^E

(

G

)

.Then x

,

d

,

a

,

b

,

xisan alternating 4-cycle inwhichab

∈

^F2,implyingthat xd

∈

^F1.Thenwehaveastrict F1-switchingpath

(

x

,

d

,

c

,

b

)

suchthat

{

^x

,

d

,

c

,

b

} < {

^a

,

b

,

c

,

d

}

^,whichisacontradictiontothe choiceof

(

a

,

b

,

c

,

d

)

.Thereforewecanassumethatb

<

d.Sinceakbk

<

abanda

,

b

<

d,wehavethat

{

^c

,

bk

,

ak

,

u

} < {

^a

,

b

,

c

,

d

}

^. As

(

c

,

b_k

,

a_k

,

u

)

isastrictswitchingpath,thiscontradictsthechoiceof

(

a

,

b

,

c

,

d

)

.

4. ProofofTheorem1forsplitgraphs

Let G be anygraphsuch that G^∗ is bipartite. Let

(

F0

,

F1

,

F2

)

be a valid3-partition of E

(

G

)

obtainedby running the algorithmofSection3onthegraphG.

Lemma5.IftherearenopentagonsinG withrespectto

(

F0

,

F1

,

F2

)

,thentherearenoswitchingpathsorswitchingcyclesinG with respectto

(

F₀

,

F₁

,

F₂

)

.

Proof. Supposenot.Let

(

a

,

b

,

c

,

d

)

bea switchingpathin G withrespectto

(

F₀

,

F₁

,

F₂

)

.Leti

∈ {

¹

,

2

}

^suchthat

(

a

,

b

,

c

,

d

)

is an Fi-switchingpath.Then we havead

∈

^E

(

G

)

,ab

,

cd

∈

^Fi

∪

^F0, andbc

∈

^F3−ⁱ.Since bc

∈

^F3−ⁱ, thereexists uv

∈

^E

(

G

)