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.