New results on the robust coloring problem

Resul s Ma h (2024) 79:122 Online Fi s c 2024 The Au ho (s) h ps://doi.o g/10.1007/s00025-024-02148-w Resul s in Ma hema ics New Resul s on he Robus Colo ing P oblem Delia Ga ijo , Albe o M´a quez, and Ra ael Robles Abs ac . Many a ia ions o he classical g aph colo ing model ha e been in ensi ely s udied due o hei mul iple applica ions; scheduling p oblems and ai c a assignmen s, o ins ance, mo i a e he obus colo ing p ob- lem. This model ge s o cap u e na u al cons ain s o hose op imiza ion p oblems by combining he in o ma ion p o ided by wo colo ings: a e - ex colo ing o a g aph and he induced edge colo ing on a subg aph o i s complemen ; he goal is o minimize, among all p ope colo ings o he g aph o a ixed numbe o colo s, he numbe o edges in he subg aph wi h he endpoin s o he same colo . The s udy o he obus colo ing model has been ocused on he sea ch o heu is ics due o i s NP-ha d cha ac e when using a leas h ee colo s, bu li le p og ess has been made in o he di ec ions. We p esen a new app oach on he p oblem ob aining he i s collec ion o non-heu is ic esul s o gene al g aphs; among hem, we p o e ha obus colo ing is he model ha be e app oaches he equi able pa i ion o he e ex se , e en when he g aph does no admi a so-called equi able colo ing. We also show he NP-comple eness o i s decision p oblem o he unsol ed case o wo colo s, ob ain bounds on he associa ed obus colo ing pa ame e , and sol e a conjec u e on pa hs ha illus a es he complexi y o s udying his colo ing model. Ma hema ics Subjec Classi ica ion. 68R10, 05C15. Keywo ds. G aph heo y, disc e e op imiza ion, g aph colo ing, obus colo ing. 1. In oduc ion Colo ing p oblems deal wi h pa i ioning he objec s o a g aph in o classes acco ding o diffe en c i e ia, and appea in many a eas wi h seemingly no 0123456789().: V,- ol 122 Page 2 o 20 D. Ga ijo e al. Resul s Ma h connec ion wi h colo ing: ime abling and scheduling [3], equency assign- men [17], egis e alloca ion [4], p in ed ci cui boa d es ing [10], pa e n ma ching [15] o analysis o biological and a cheological da a [2]; see also [16] o desc ip ions o he fi s ou men ioned applica ions. The classical colo ing p oblem uses p ope colo ings: a k-p ope colo ing is an assignmen o kcolo s o he e ices o a g aph so ha no edge has bo h endpoin s o he same colo . This is an NP-ha d p oblem o h ee o mo e colo s (and polynomial o wo colo s), which has ecei ed a la ge a en ion in he li e a u e, no only o i s eal wo ld applica ions, bu also o i s heo e ical aspec s and compu a ional difficul y; see, o ins ance [5,9]. O he diffe en c i e ia ha e been conside ed in colo ing p oblems as he equi able pa i ion, ha is, pa i ioning he e ex se o a g aph in o equal o almos equal subse s. Fo mally, a g aph is equi able k-colo able i i admi s a k-p ope colo ing such ha he ca dinali ies o any wo colo classes diffe by a mos one. Equi able colo ing o g aphs was in oduced by Meye [14] o modeling p oblems in an ope a ions esea ch con ex , and has since been widely in es- iga ed due o i s many p ac ical applica ions in sequencing and scheduling; see o example [8] and he e e ences he ein, in pa icula , [7] o a specific applica ion in scheduling. As explained in [8], his ype o colo ing models si ua ions in which one desi es o spli a sys em in o equal o almos equal conflic - ee subsys ems. Howe e , no e e y sys em admi s such a di ision, and o he c i e ia a e needed in o de o app oach as much as possible he equi able pa i ion; he e a ises he obus colo ing p oblem (RCP, o sho ) ha can be s a ed as ollows: Le G=(V(G),E(G)) be an unweigh ed and simple g aph wi h ch oma ic numbe χ(G). Gi en a subg aph Ho i s complemen g aph Gand a posi i e in ege k≥χ(G), find a k-p ope colo ing φ o G ha minimizes, o e all hose k-p ope colo ings, he numbe o monoch oma ic edges1in he induced colo ing on H. We say ha φis a k- obus colo ing o (G, H), and m(G, H, k) is such minimum. The o iginal s a emen o he p oblem in oduced in [19] conside s H o be a weigh ed g aph, and he goal is o minimize he sum o he weigh s o he monoch oma ic edges. Ou s a emen es ablishes all edge weigh s in H o be 1, as bo h e sions a e equi alen o mos o he ques ions add essed in his wo k, and o hose ha a e no , ou a gumen s can be adap ed. We will be mo e p ecise on his issue in each o he sec ions below, once he diffe en p oblems ha we app oach ha e been desc ibed in de ail. Applica ions o obus colo ing a e summa ized in [12,19]; among hem, i highligh s applica ions o ime abling and scheduling p oblems, geog aphical maps, and ai c a assignmen . Fo example, he ai c a assignmen p oblem 1Monoch oma ic edges a e hose whose endpoin s ha e he same colo ; o he wise he edges a e called bich oma ic. New Resul s on he Robus Colo ing P oblem Page 3 o 20 122 can be modeled as a g aph colo ing p oblem whe e each e ex in he g aph G ep esen s a fligh ou e and each colo ep esen s one ai c a . The e is an edge be ween wo e ices i an ai c a canno se e he wo fligh ou es ep- esen ed by he wo e ices. I fligh -delays a e aken in o accoun , he o e lap ela ionship be ween fligh ou es changes, and his in o ma ion is cap u ed by he edges o a new g aph H. The monoch oma ic edges in H ep esen can- celled fligh s, and he goal is o minimize he numbe o fligh s ha mus be cancelled when he e a e kai c a s. Rela ed wo k. As i was men ioned be o e, he RCP was in oduced in [19], whe e he au ho s also desc ibe se e al applica ions o his colo ing model, and conclude ha he decision p oblem is NP-comple e o k≥3. They also p esen a bina y p og amming model and ou line a gene ic algo i hm. Due o hei complexi y esul , mos pape s in he opic sea ch o heu is ics. In [18] he au ho s de elop se e al me a-heu is ics o sol e he RCP including gene ic algo i hm, simula ed annealing and abu sea ch. A column gene a ion- based heu is ic algo i hm is p esen ed in [20]. A s udy on he obus ai c a assignmen is de eloped in [12]; he au ho s p opose new echniques o an app oxima e solu ion o he p oblem, such as he pa i ion based encoding and se e al me a-heu is ics (local sea ch, simula ed annealing, abu sea ch and hyb id me hod). O he e e ences in his di ec ion a e [1,6]. Almos no p og ess has been made in o he di ec ions: we can only e e he eade o [13] o a heo e ical s udy on he RCP o he case o Gand Hbeing pa hs on he same se o e ices and he alue k= 3. The au ho s p esen an exac bu exponen ial algo i hm o find a 3- obus colo ing o (G, H), and a andomized algo i hm and a g eedy algo i hm analyzing he cos o hei ou pu . They also apply hei andomized algo i hm o ob ain bounds on he p oblem o maximizing he sum o he weigh s (cos s) o he monoch oma ic edges o H, and pose wo conjec u es ela ed wi h bounding he numbe o monoch oma ic edges o Hinduced by a 3-colo ing o G. Ou esul s. We p esen a non-heu is ic app oach o he RCP o gene al g aphs. In Sec . 2, we fi s p o e ha obus colo ing is he model ha be e app oaches he equi able pa i ion e en when he g aph has no equi able col- o ing; i he g aph admi s such a colo ing, we ex end he known connec ion be ween obus colo ings o (G, G) and equi able colo ings o G o a b oad class o subg aphs H. The NP-comple e na u e o he decision p oblem o o- bus colo ing is hen es ablished in Sec . 2.1 o he unsol ed case o wo colo s, in con as o he co esponding decision p oblems o classical g aph colo ing and equi able colo ing. Sec ion 2.2 ocuses on he modifica ions equi ed by he g eedy algo i hm o classical g aph colo ing in o de o gua an ee an op imal solu ion ( o some e ex o de ing) when dealing wi h obus colo ings and equi able colo ings. We in oduce he obus -g eedy algo i hm as he a ia ion sa is ying ha p ope y. This algo i hm is key in Sec . 3, whe e we fi s ob ain a igh uppe bound on m(G, H, k) o a bi a y g aphs Gand subg aphs H, 122 Page 4 o 20 D. Ga ijo e al. Resul s Ma h a b c d e a b d e a d e a b c d e K3,3K3,3=K3,3[S]K3,3[S] S={a, b, d, e, } K3,3[S] S ={a, d, e, } S=V(K3,3) Figu e 1. A 3-colo ing o K3,3, and he induced edge colo - ings in K3,3,K3,3[S], and K3,3[S]; he se s Sand S admi an equi able 3-colo ing, and Sdoes no and hen o g aphs defined as α-g eedy o ien able ( his includes ees, some se ies–pa allel g aphs and bipa i e ou e plana g aphs). In Sec . 4,wep o e in he affi ma i e a conjec u e posed by L´opez-B acho e al. [13]onm(G, H, 3) o Gand Hbeing wo pa hs on he same se o e ices, and ex end he esul o Hbeing a e ex-disjoin union o pa hs; he solu ion o his conjec u e illus a es e y well he complexi y o dealing wi h obus colo ings. We assume k<min{|V(G)|,χ(G)χ(H)} o o he wise m(G, H, k)=0as he e a e always enough colo s o ob ain a p ope colo ing in Gand also in H. In addi ion, o sho , we omi he e m p ope and simply say colo ing when no con usion may a ise. 2. Robus Colo ings as an App oach o Equi able Colo ings When a g aph Ghas an equi able colo ing, one ob ains a uni o m dis ibu ion o colo s on he e ices, and he ques ion is whe he his dec eases he numbe o monoch oma ic edges in a subg aph Ho G, bu his ques ion can no be answe ed o an a bi a y Has he answe would comple ely depend on i s s uc u e. Thus, i makes sense o s udy he connec ion be ween equi able colo ings and obus colo ings when His he whole G. In his sec ion, we go u he by se ing Has he induced subg aph in Gby a subse o e ices S⊆V(G). We deno e his g aph as G[S], see Fig. 1 o some examples. Fo g aphs G ha admi an equi able colo ing, i is known ha a k- colo ing o Gis equi able i and only i i is a k- obus colo ing o (G, G); his can be deduced, o ins ance, om [19, P oposi ion 3.1]. We fi s p o e ha , e en i Gdoes no admi an equi able colo ing, obus colo ing is he model ha be e app oaches he uni o m dis ibu ion o colo s. Le S⊆V(G), and conside he colo classes C1,...,C k ha pa i ion V(G)byak-colo ing φo G(each class con ains he e ices wi h he co e- sponding colo ). Le Pφ,S =(n1,...,n k) be he pa i ion o |S|associa ed o he colo ing φ, whe e ni=|Ci∩S|. We say ha φis equi able o e Si Pφ,S sa isfies ha |ni−nj|≤1 o 1≤i, j ≤k; wi h some abuse o he language, we may indis inc ly say ha Sadmi s an equi able k-colo ing (see Fig. 1). The e New Resul s on he Robus Colo ing P oblem Page 5 o 20 122 a e monoch oma ic edges in he induced edge colo ing o G[S] i and only i ni>1 o some 1 ≤i≤k; each pai o e ices o Sin he same colo class Ci de e mines a monoch oma ic edge, and so he o al numbe o monoch oma ic edges induced by he pa i ion Pφ,S in G[S], deno ed by m(Pφ,S), is m(Pφ,S)=  1≤i≤k,ni>1ni 2,(1) which can be ew i en as m(Pφ,S)=1 2 k  i=1 (n2 i−ni)=1 2 k  i=1 ni−1 22 −1 4=−k 8+1 2d2(Pφ,S,Q), whe e d(Pφ,S,Q) is he Euclidean dis ance be ween he poin Pφ,S=(n1,...,n k) and he poin Q=( 1 2,...,1 2)inak-dimensional space. (No e ha , in he abo e equa ion, we include in he sum he case ni= 1 since n2 i−ni= 0.) We can hus conclude ha m(Pφ,S) is mimimum o e all k-colo ings φ o Gi and only i d(Pφ,S ,Q) is minimum. Hence, minimizing he numbe o monoch oma ic edges in he induced colo ing o G[S] is equi alen o finding he poin Pφ,S in he hype plane desc ibed by he equa ion n1+n2+...+ nk=|S| ha minimizes he dis ance o Q. Fu he , d(Pφ,S ,Q) is minimum i and only i d(Pφ,S ,P |S|,k) is minimum, whe e P|S|,k =( |S| k,...,|S| k)is he o hogonal p ojec ion o Qon o ha hype plane. Obse e ha P|S|,k ep esen s he ideal uni o m dis ibu ion in o he kcolo classes. This dis ibu ion may no exis (|S|migh no e en be di isible by k) bu we ha e shown ha he k- obus colo ing is he closes o i unde he Euclidean me ic; his is he con en o he ollowing heo em. Theo em 2.1. Ak-colo ing φo a g aph Gis a k- obus colo ing o (G, G[S]) i and only i d(Pφ,P |S|,k)is minimum o e all k-colo ings o G. Conside now a k- obus colo ing φo (G, G[S]) and he pa i ion Pφ,S = (n1,...,n k). Suppose ha ni<n j o some 1 ≤i, j ≤k, and le P= (n1,...,n i+1,...,n j−1,...n k); his is a k-pa i ion o |S| ha is no nec- essa ily associa ed o a k-colo ing bu , wi h some abuse o no a ion, we se m(P)as m(P)=ni+1 2+nj−1 2+ =i,j n 2. By Eq. (1), we ha e m(Pφ,S )−m(P)=nj−ni−1≥0, and so m(Pφ,S )≥m(P). The e o e, any pa i ion o |S|sa is ying ha any wo o i s elemen s diffe by a mos one is a minimum o he unc ion m(·) o e all k-pa i ions o |S|. Thus, we ha e p o ed he ollowing p oposi ion, whe e we also gi e he minimum alue o he unc ion m(·), which is s aigh o wa d. 122 Page 6 o 20 D. Ga ijo e al. Resul s Ma h P oposi ion 2.1. Fo e e y k≥χ(G)i holds ha : m(G, G[S],k)≥(k− )s 2+ s+1 2, whe e s=|S| kand =|S|−sk. Mo eo e , he bound is igh i and only i Sadmi s an equi able k-colo ing. The p eceding lowe bound is he numbe o monoch oma ic edges in he induced edge colo ing o G[S] by an equi able k-colo ing o e S, i i exis s. Thus, we ex end he known connec ion be ween equi able colo ings and obus colo ing o he g aph G[S]. Theo em 2.2. Le S⊆V(G)be a subse o e ices ha admi s an equi able k-colo ing. Then, a k-colo ing φo Gis equi able o e Si and only i φis a k- obus colo ing o (G, G[S]). We nex illus a e he p e ious esul s wi h some examples. Example 2.1. Figu e 2shows a 4-equi able colo ing o a g aph G, which by he ela ion be ween equi able colo ings and obus colo ings, is a 4- obus colo ing o (G, G). The p oblem a ises when a g aph has no equi able colo ing o some alue k. This happens o he comple e bipa i e g aph K3,3when se ing k=3 since any 3-colo ing gene a es colo classes C1,C 2,C 3o ca dinali y 1,2,3, espec i ely. See Fig. 1. Theo em 2.1 es ablishes ha he closes pa i ion o he e ex se o an equi able pa i ion is gi en by a 3- obus colo ing o (G, G). Fu he , Theo em 2.2 allows us o s udy he scena io o subse s So e ices in K3,3. All subse s Scon aining a mos wo e ices o class C3admi an equi able 3-colo ing. Mo eo e , m(G, G[S],3) is ei he 1 o 2 (depending on he se Sconside ed). Example 2.2. The a gumen o p o e P oposi ion 2.1 can be used o ob ain obus colo ings o (G, G[S]) when he g aph Gdoes no admi equi able col- o ings. Fo ins ance, he wheel g aph W1,7wi h 8 e ices has no equi able colo ings as he e is always a colo class o ca dinali y 1 (de e mined by he cen al e ex). Fo k= 4, he abo e men ioned a gumen es ablishes ha he pa i ion (1,1,3,3) can no be associa ed o a 4-colo ing o W1,7 ha is a 4- obus colo ing o (W1,7, W1,7), bu (1,2,2,3) gi es such a obus colo ing. 2.1. Complexi y o Robus Colo ings The classical g aph colo ing decision p oblem is NP-comple e o k≥3 colo s, bu polynomial o k=2[9]. The same happens o equi able k-colo ing [8]. Now, conside he ollowing p oblem: Robus -Colo ing Ins ance: Ag aphG, a subg aph Ho G, a posi i e in ege k≤|V(G)|,and m∈N. New Resul s on he Robus Colo ing P oblem Page 7 o 20 122 Figu e 2. Ag aphG ha admi s 4-equi able colo ings (as he one shown), which a e 4- obus colo ings o (G, G). None o hem can be ob ained by he g eedy algo i hm wi h any o he 8! possible e ex o de ings Ques ion: Does a k-colo ing o Gexis such ha he numbe o monoch oma ic edges in he induced colo ing on His a mos m? A educ ion o g aph colo ing shows he NP-comple eness o Robus -Colo ing o k≥3[19, P oposi ion 3.2]. We nex p o e ha , su p isingly, his decision p oblem is NP-comple e e en o k=2. Theo em 2.3. Robus -Colo ing is an NP-comple e p oblem o k=2. P oo . The p oblem is in NP since one can compu e in polynomial ime he numbe o monoch oma ic edges induced in Hby a gi en k-colo ing o G, and check whe he his numbe is a mos m. Conside now he ollowing NP-comple e p oblem [11]: Simple-Max-Cu Ins ance: Ag aphG=(V,E), ∈N. Ques ion: Does he e exis a se S⊂Vsuch ha |{su ∈E|s∈S, u ∈ V−S}| ≥ ? We nex educe Simple-Max-Cu o ou decision p oblem, hus p o ing he esul . Le G=(V,E) be a g aph wi h n e ices, and le ∈N.Le Vnbe he i ial g aph wi h n e ices (i.e., i has no edges); he g aph Gis a subg aph o Vn. Any 2-colo ing o Vninduces a pa i ion o Vin o wo subse s Sand V−S such ha he bich oma ic edges in he induced colo ing on Ga e p ecisely he se {su ∈E|s∈S, u ∈V−S}. The e o e, |{su ∈E|s∈S, u ∈V−S}| ≥ ⇐⇒ m(Vn,G,2) ≤|E|−. The inequa ion m(Vn,G,2) ≤|E|−is equi alen o he exis ence o a 2- colo ing o Vnsuch ha he numbe o monoch oma ic edges in he induced colo ing on Gis a mos |E|−. 2.2. Robus -G eedy Algo i hm Fo classical g aph colo ing, i is well-known ha he e always exis s a e ex o de ing in any g aph such ha he g eedy algo i hm2gi es an op imal p ope 2Recall ha he g eedy algo i hm o g aph colo ing conside s an o de ing o he e ices o he g aph and assigns o each e ex i s i s a ailable colo (i.e., he i s colo ha has no been assigned o any o i s al eady colo ed neighbou s). 122 Page 8 o 20 D. Ga ijo e al. Resul s Ma h colo ing, ha is, a p ope colo ing using he minimum numbe o colo s. How- e e , his is no ue o obus colo ing, and nei he o equi able colo ing as he example in Fig. 2shows. We nex in oduce a a ia ion o he g eedy algo i hm, called he obus -g eedy algo i hm, which cap u es he cons ain s o he obus colo ings and gi es, o some o de ing o he e ices o any g aph, he closes pa i ion o he equi able pa i ion. Fu he , his algo i hm will lead, oge he wi h he no ion o α-g eedy o ien able g aph (in oduced in Sec . 3.1), o uppe bounds on m(G, H, k) o well-known amilies o g aphs G and a bi a y subg aphs Ho G. As he classical g eedy algo i hm o g aph colo ing, he obus -g eedy algo i hm also p ocesses he e ices o a g aph Gin a gi en o de ing, and he e is an o de ed lis o colo s ( hey a e simply aken in o de ). In addi ion, we mus keep ack o he numbe o monoch oma ic edges on a fixed subg aph Ho G. Robus -g eedy algo i hm Each e ex o Gis gi en he fi s colo co he lis sa is ying he wo ollowing p ope ies: (a) colo cis a ailable o , i.e., i has no been assigned o he al eady colo ed neighbou s o in G; (b) i minimizes, among all a ailable colo s o , he numbe o monoch oma ic edges on Hwi h as an endpoin . The algo i hm s ops when all e ices o Gha e been colo ed. As we poin ed ou be o e, some ques ions on obus colo ing canno be app oached o gene al subg aphs Ho Gsince he answe would depend on he s uc u e o H, and i makes hen sense o se H=G. This happens in he ollowing heo em. Theo em 2.4. Le Gbe a g aph, and le k≥χ(G)be a posi i e in ege . The e always exis s a e ex o de ing o Gsuch ha he obus -g eedy algo i hm p o- ides a k- obus colo ing o (G, G). P oo . Le φbe a k- obus colo ing o (G, G), and conside he colo classes Ci={ui 1,...,u i ni},1≤i≤k,inwhichφpa i ions V(G). Assume ha he classes a e o de ed by inc easing ca dinali y: ni≤nj o 1 ≤i<j≤k. Le Obe a e ex o de ing ob ained by choosing a e ex om each class Ciin a cyclic way (in inc easing o de ) un il he e a e no e ices le in any o he classes, o example, Ocould be: u1 1,u 2 1,...,u k 1,u 1 2,u 2 2,...,u k 2,...,u 1 n1,..., uk n1,u 2 n1+1,...,u k n1+1,...,u k nk. The obus -g eedy algo i hm assigns colo 1 o u1 1( he same fi s colo as φ), and when i p ocesses u2 1i may happen ha : (i) u1 1u2 1∈E(G)and so u2 1would be assigned colo 2 by condi ion (a) o he algo i hm, o (ii) u1 1u2 1∈E(G) and so, by condi ion (b) o he algo i hm, u2 1would also be assigned colo 2 ( his colo minimizes, among colo s 1 and 2, he numbe o monoch oma ic edges in Gwi h u2 1as endpoin ). Hence, he obus -g eedy New Resul s on he Robus Colo ing P oblem Page 9 o 20 122 algo i hm assigns he same colo s as φ o u1 1and u2 1. This a gumen can be ex ended o he fi s kn1 e ices, o which he algo i hm assigns he same colo s as φgene a ing kcolo classes wi h he same size n1(a e p ocessing he e ices u1 1,u 2 1,...,u k 1,...,u 1 n1,...,u k n1o he o de ing O). Now, he algo i hm could assign he same colo s as φ o he emaining e ices bu , i a some la e s age, he obus -g eedy algo i hm assigns o a e ex a diffe en colo han ha assigned by φ, we s op he algo i hm and colo he emaining e ices wi h he same colo s as φ, ob aining a new k-colo ing ψ. The associa ed pa i ions Pφ,V (G)and Pψ,V (G)only diffe in one elemen : oughly speaking, one e ex has changed om a bigge colo class o a smalle one. Following he same a gumen as o P oposi ion 2.1, we ob ain ha m(Pφ,V (G))≥m(Pψ,V (G)). Since φis a obus colo ing hen m(Pφ,V (G))=m(Pψ,V (G)). Fo each change o colo p oduced by he obus - g eedy algo i hm, we can a gue as abo e ob aining a sequence o k- obus colo ings o (G, G) ha lead o he desi ed k- obus colo ing gene a ed by he algo i hm.  The analogous o Theo em 2.4 o equi able pa i ions o e ex se s is ob ained om Theo em 2.2 by se ing S=V(G). Co olla y 2.1. Fo e e y equi able k-colo able g aph G, he e always exis s a e ex o de ing such ha he obus -g eedy algo i hm p o ides an equi able k- colo ing o i s e ices. 3. Uppe Bounds on m(G, H, k) o A bi a y H In his sec ion we deal wi h a bi a y subg aphs Ho G.3We fi s p esen a igh uppe bound on m(G, H, k) o e e y g aph G, o which we need he ollowing echnical lemma, whe e wo dis inc colo ings a e conside ed, one o hem no necessa ily p ope . Thus, o a oid any con usion, he e m p ope will no be omi ed in Lemma 3.1 and Theo em 3.1. Lemma 3.1. Le ≥2. Fo e e y p ope -colo ing o a g aph Gand e e y posi i e in ege ∈[1, ] he e exis s a -colo ing o G ha induces a mos |E(G)|·2( − ) monoch oma ic edges in G. P oo . The esul is s aigh o wa d o =1as|E(G)|is he numbe o monoch oma ic edges induced by any 1-colo ing o Gand 2( −1) ≥1 o ≥2. I = he esul es ablishes ha he e a e no induced monoch oma ic edges, which is ue o any p ope -colo ing o G. Assume now ha 1 < < , and le φbe a p ope -colo ing o G,which induces an edge colo ing o G(acco ding o he colo s o he endpoin s o he 3Ou esul s conside H o be unweigh ed bu ou a gumen s can be easily adap ed o mul ig aphs and g aphs wi h a ional edge weigh s; in he case o eal edge weigh s, we can app oxima e hem (using a ional weigh s) wi h he desi ed p ecision. 122 Page 16 o 20 D. Ga ijo e al. Resul s Ma h Suppose now ha s=0.Le {u1,...,u n}be he se o e ices o he pa h G( iewed as an ho izon al pa h) o de ed om le o igh . We dis inguish h ee cases. Case 1:The e is a e ex ui,i=n,sa is ying ha he e exis s a unique edge ujukin Hsuch ha j<iand k>i(one endpoin o he edge is o he le and he o he o he igh o ui). We p oceed by induc ion on n.Le G1and G2be, espec i ely, he sub-pa hs o Gon e ices {u1,...,u i}and {ui+1,...,u n}, ha is,G=G1∪G2∪{uiui+1}. Simila ly, we conside he g aph H=H1∪H2∪{ujuk}, whe e Hiis he subg aph o Hcon ained in Gi.E e y 3- obus colo ing o (G, H) can be modified o make he edge ujukbich oma ic: i suffices o main ain he colo ing o G1and change he colo o ukwi h o he colo in G2, i needed. Thus, m(G, H, 3) = m(G1,H 1,3) + m(G2,H 2,3), and by induc ion he esul ollows. Case 2: Ve ex unhas deg ee h ee in G∪H. Again, we use induc ion on n. Le e1,e 2be he wo edges o Hinciden wi h un. S a ing om un−1, om igh o le , conside he wo fi s igh endpoin s uk,u j,j≤k, o edges in H; he co esponding edges a e deno ed, espec i ely, by e3and e4.Le G1 be he sub-pa h o Gon e ices {u1,...,u j}, and le H1⊂G1be ei he H {ei|1≤i≤3}(i uk=uj)o H {ei|1≤i≤2}(i uk=uj). The diffe ence be ween a 3- obus colo ing o (G, H)andoneo (G1,H 1) elies on a mos one edge mo e ha can be monoch oma ic. Indeed, once he e ices o G1ha e been colo ed, we colo he e ices om un o uj+1: he e is one a ailable colo o un o make e1and e2bich oma ic, and he induced colo ing on e4always comes om he colo ing in G1.Thus,e3would be he unique edge ha could inc ease he numbe o monoch oma ic edges when uk=uj. Hence, m(G, H, 3) ≤m(G1,H 1,3) + 1, and he desi ed bound is ob ained by induc ion. Case 3: The pai (G, H)sa is ies nei he case 1 no case 2.Wep esen a e ex colo ing p ocedu e in which we fi s go om le o igh assigning colo s o he e ices so ha as long as possible no monoch oma ic edge is gene a ed in G∪H. I we can colo all he e ices, hen m(G, H, 3) = 0; o he wise a sa u a ed e ex ui,3<i<n, is ound: a e ex is sa u a ed i i s deg ee in G∪His ou and, when i is fi s isi ed, h ee o i s neighbou s ha e al eady been colo ed wi h he h ee a ailable colo s. In his case, e ex uiis no assigned a colo , and we con inue isi ing e ices wi hou colo ing un il he fi s condi ioned e ex ujis ound: a non-colo ed e ex (a some s age) ujis condi ioned i i is an endpoin o an edge o Hwhose o he endpoin u has al eady been colo ed ( <i); he edge u ujis said o be semi-colo ed. Obse e ha a his s age e ices om u1 o ui−1a e colo ed, and hose om ui o una e no (including uj). No e also ha e ex ujmus exis as s=0 and ui=un. As an example, in Fig. 7, e ex uiis sa u a ed and e ices uj and uka e condi ioned. We nex desc ibe how ou p ocedu e ob ains a p ope colo ing o Gwi h he p ope y ha he o al numbe o monoch oma ic edges in Hequals he New Resul s on he Robus Colo ing P oblem Page 17 o 20 122 numbe o sa u a ed e ices ound du ing he p ocess. Mo e conc e ely, when a sa u a ed e ex is isi ed, he e a e ou o fi e edges o Hin ol ed o which only one has o be monoch oma ic. I e ex ujhas wo semi-colo ed edges e1and e2, we fi s assign a colo o uj o make bo h edges bich oma ic. Then, e ices om uj−1 o uia e colo ed ( om igh o le ) o main ain he p ope colo ing in G; his gi es one monoch oma ic edge among he wo edges o Hinciden wi h ui. Assume now ha ujhas a unique semi-colo ed edge e1, and le ukbe he fi s ( om le o igh ) condi ioned e ex in {uj+1,...,u n}; his e ex mus exis since o he wise e1would be he unique edge wi h one endpoin o he le and he o he o he igh o ui(case 1). I ukhas wo semi-colo ed edges e2and e3(see Fig. 7a), we fi s colo ukand ujso ha edges ei,1≤i≤3 a e bich oma ic. Then, om igh o le , e ices {uk−1,...u j+1}and {uj−1,...u i}can be p ope ly colo ed. Finally, suppose ha e ex ukhas a unique semi-colo ed edge e2. (i) I ujhas ei he deg ee 3 in G∪Ho an inciden edge e3wi h he o he endpoin ube ween uiand uj(i<<j), we fi s isi , om igh o le , e ices {uk,...,u j}assigning colo s o make e1and e2bich oma ic. Then we colo , again om igh o le , {uj−1,...,u i}so ha e3(i i exis s) is bich oma ic; his is possible since we a e colo ing om igh o le so, when uis isi ed, he e a e wo a ailable colo s. Re e o Fig. 7b. (ii) I ujhas an inciden edge e3wi h he o he endpoin ube ween ujand uk(j<<k), we andomly assign o ukone o he wo colo s ha make e2bich oma ic, and p oceed o colo om igh o le e ices {uk−1,...,u j} using only he colo o ukand ha o he o he endpoin o e2. Ou aim is ha e1and e3a e bich oma ic, bu i may happen ha , wi h ou assignmen , hey can no be bo h bich oma ic while main aining he p ope colo ing in G; his happens o example gi ing colo 1 o ukin Fig. 7c. In his case, we change he colo o all e ices in {uk,...,u j+1} ha ha e he same colo as ukby he o he colo ha p ese es e2as bich oma ic (in ou example, we would change colo 1 by colo 3). Then, we colo e ices om uj−1 o ui. We hus conclude ha , when a sa u a ed e ex is isi ed, ou p ocedu e gene a es one monoch oma ic edge in H, and a leas h ee bich oma ic ones. Hence, m(G, H, 3) ≤|E(H)| 4. Figu e 6illus a es examples o s=0and s>0 whe e he bound is igh .  5. Concluding Rema ks In his wo k we ha e p esen ed he fi s non-heu is ic s udy o gene al g aphs on he obus colo ing model. We del ed in o he connec ion bee ween obus colo ings and equi able colo ings, encompassing a complexi y s udy. We also ob ained he fi s gene al bounds on he pa ame e m(G, H, k), and sol ed an in iguing conjec u e on pa hs. These a e impo an s eps on his difficul 122 Page 18 o 20 D. Ga ijo e al. Resul s Ma h uiuj e1e2 32 11212 3 uk (a) e3 uiuj e1e2 32 11212 3 uk (b) e3 u uiuj e1e2 32 11212 3 uk (c) e3 u Figu e 7. Edges o Gin black, and edges o Hin ed; e ices {u1,...,u i−1}ha e al eady been colo ed (colo s 1–3). Ve ex ukhas wo semi-colo ed edges in (a)andonein(b) and (c); he diffe ence be ween hese wo cases is he posi ion o he endpoin uo e3 and challenging p oblem ha lea e diffe en ypes o open ques ions o u u e esea ch: •The p oblem o deciding whe he a gene al g aph has an equi able k- colo ing wi h a gi en numbe o colo s k≥3 is NP-comple e [8]. How- e e , i would be in e es ing o find a b oad class o g aphs o which a polynomial ime algo i hm could be designed. The algo i hm could also be applied o obus colo ing by means o Theo em 2.2. •In o de o imp o e he uppe bounds o Sec . 3, we hink ha new ech- niques mus be de eloped, a he han ying o enhance hem by using a simila app oach o he one p esen ed in his pape . •The p oo o Theo em 4.1 shows he complexi y o s udying he RCP e en o pa hs. Thus, o a be e unde s anding o his colo ing model, i would be wo h s udying i he ideas o ha p oo could be ex ended o o he amilies o g aphs. Au ho con ibu ions All au ho s con ibu ed o he manusc ip equally. Funding Funding o open access publishing: Uni e sidad de Se illa/CBUA D.G. and A.M. we e suppo ed by p ojec PID2019-104129GB-I00 unded by New Resul s on he Robus Colo ing P oblem Page 19 o 20 122 MICIU/AEI/10.13039/501100011033 and PID2019-104129GB-I00/MCIN/AEI/ 10.13039/501100011033. Da a a ailabili y Da a sha ing no applicable o his a icle as no da ase s we e gene a ed o analyzed du ing he cu en s udy. Decla a ions Con lic o in e es No conflic s o in e es epo ed o his wo k. Open Access. This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which pe mi s use, sha ing, adap a ion, dis ibu ion and e- p oduc ion in any medium o o ma , as long as you gi e app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence, and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included in he a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I ma e ial is no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed by s a u o y egu- la ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he copy igh holde . To iew a copy o his licence, isi h p://c ea i ecommons. o g/licenses/by/4.0/. Re e ences [1] A che i, C., Bianchessi, N., He z, A.: A b anch-and-p ice algo i hm o he obus g aph colo ing p oblem. Disc e e Appl. Ma h. 165, 49–59 (2014) [2] Ba helemy, J.P., Guenoche, A.: T ees and P oximi y Rep esen a ions. Wiley, New Yo k (1991) [3] Bu ke, E.K., McCollum, B., Meisels, A., Pe o ic, S., Qu, R.: A g aph-based hype -heu is ic o educa ional ime abling p oblems. Eu . J. Ope . Res. 176(1), 177–192 (2007) [4] Chai in, G.J.: Regis e alloca ion and spilling ia g aph colo ing. In: SIG- PLAN’82 Symposium on Compile Cons uc ion, Bos on, Mass., pp. 98–105 (1982) [5] Cha and, G., Zhang, P.: Ch oma ic G aph Theo y, 2nd edn. CRC P ess, Boca Ra on (2020) [6] Dey, A., P adhan, R., Pal, A., Pal, T.: The uzzy obus g aph colo ing p oblem. In: P oceedings o he 3 d In e na ional Con e ence on F on ie s o In elligen Compu ing: Theo y and Applica ions (FICTA) 2014, pp. 805–803 (2014). Pa o he Ad ances in In elligen Sys ems and Compu ing Book Se ies (AISC, olume 327) [7] Fu ma´nczyk, H.: Equi able colo ing o g aph p oduc s. Opusc. Ma h. 26(1), 31– 44 (2006) [8] Fu ma´nczyk, H., Jas zebski, A., Kubale, M.: Equi able colo ings o g aphs. Recen heo e ical esul s and new p ac ical algo i hms. A ch. Con ol Sci. 26, 281–295 (2016) 122 Page 20 o 20 D. Ga ijo e al. Resul s Ma h [9] Ga ey, M.R., Johnson, D.S.: Compu e s and In ac abili y: A Guide o he The- o y o NP-Comple eness. W.H. F eeman, New Yo k (1979) [10] Ga ey, M.R., Johnson, D.S., So, H.C.: An applica ion o g aph colo ing o p in ed ci cui es ing. IEEE T ans. Ci cui s Sys . 23, 591–599 (1976) [11] Ga ey, M.R., Johnson, D.S., S ockmeye , L.: Some simpli ied NP-comple e g aph p oblems. Theo . Compu . Sci. 3(1), 237–267 (1976) [12] Lim, A., Wang, F.: Robus g aph colo ing o unce ain supply chain manage- men . In: P oceedings o he 38 h Annual Hawaii In e na ional Con e ence on Sys em Sciences (HICSS’05), ol. 3, pp. 81b (2005) [13] L´opez-B acho, R., Ram´ı ez, J., Za agoza-Ma ´ınez, F.J.: Algo i hms o obus g aph colo ing on pa hs. In: P oceedings o he 2nd In e na ional Con e ence on Elec ical and Elec onics Enginee ing, pp. 9–12 (2005) [14] Meye , W.: Equi able colo ing. Am. Ma h. Mon. 80, 920–922 (1973) [15] Ogawa, H.: Labeled poin pa e n ma ching by Delaunay iangula ion and max- imal cliques. Pa e n Recogn. 19(1), 35–40 (1986) [16] Pa dalos, P.M., Ma idou, T., Xue, J.: The g aph colo ing p oblems: a biblio- g aphic su ey. In: Handbook o Combina o ial Op imiza ion, ol. 2, pp. 331– 395. Kluwe Academic Publishe s (1998) [17] Smi h, D.H., Hu ley, S.: Bounds o he equency assignmen p oblem. Disc e e Ma h. 167–168, 571–582 (1997) [18] Wang, F., Xu, Z.: Me aheu is ics o obus g aph colo ing. J. Heu is ics 19, 529–548 (2013) [19] Y´a˜nez, J., Ram´ı ez, J.: The obus colo ing p oblem. Eu . J. Ope . Res. 148, 546–558 (2003) [20] Y¨uceo˘glu, B., Sahin, G., an Hoesel, S.P.M.: A column gene a ion based algo- i hm o he obus g aph colo ing p oblem. Disc e e Appl. Ma h. 217, 340–352 (2017) Delia Ga ijo, Albe o M´a quez and Ra ael Robles Depa amen o de Ma em´a ica Aplicada I Uni e sidad de Se illa A da. Reina Me cedes s/n 41012 Se ille Spain e-mail: [email p o ec ed]; [email p o ec ed]; [email p o ec ed] Recei ed: May 28, 2023. Accep ed: Feb ua y 7, 2024. Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic- ional claims in published maps and ins i u ional affilia ions.