A complexity dichotomy for critical values of the b-chromatic number of graphs

(1)

Contents lists available atScienceDirect

Theoretical Computer Science

www.elsevier.com/locate/tcs

A complexity dichotomy for critical values of the b-chromatic number of graphs

Lars Jaffke

^∗,¹

, Paloma T. Lima

^∗,²

DepartmentofInformatics,UniversityofBergen,Bergen,Norway

a rt i c l e i n f o a b s t ra c t

Articlehistory:

Received12July2019

Receivedinrevisedform30January2020 Accepted8February2020

Availableonline12February2020 CommunicatedbyL.M.Kirousis

Keywords:

b-coloring b-chromaticnumber Complexitydichotomy

Ab-coloringofagraph G isaproper coloringofitsverticessuch thateachcolorclass contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has a b-coloring with k colors. The b- chromaticnumberofagraphG,denotedby

χ

b(G),isthemaximumnumberksuchthatG admitsab-coloringwithkcolors.Weconsiderthecomplexityoftheb-Coloringproblem, wheneverthevalue ofkis closetooneoftwo upperbounds on

χ

b(G):The maximum degree (G) plus one, and the m-degree, denoted by m(G), which is defined as the maximum number i such that G has i vertices ofdegree at least i−^1. ^We ôbtainâ dichotomyresultforallfixedk∈Nwhenkisclosetooneofthetwoabovementioned upperbounds.Concretely,weshow thatifk∈ {(G)+¹−^p,m(G)−^p}^,^the^problemîs polynomial-time solvable whenever p∈ {⁰,1} ând,êven ^when ^k=^3,ît îs NP-complete whenever p≥^2.^We furthermoreconsiderparameterizationsoftheb-Coloringproblem thatinvolvethemaximumdegree(G)oftheinputgraphGandgivetwoFPT-algorithms.

First, weshow that deciding whether agraph G has ab-coloring with m(G) colors is FPTparameterizedby(G).Second,weshowthatb-ColoringisFPTparameterizedby (G)+k(G),wherek(G)denotesthenumberofverticesofdegreeatleastk.

©²⁰²⁰^TheÂuthor(s).^Published^byÊlsevier^B.V.^Thisîsânôpenâccessârticleûnder^the CCBYlicense(http://creativecommons.org/licenses/by/4.0/).

1. Introduction

Givenasetofcolors,apropercoloringofagraphisan assignmentofacolortoeach ofits verticesinsuch awaythat no pairofadjacentverticesreceivethesamecolor.InthedeeplystudiedGraphColoringproblem,we aregivenagraph andthequestionistodeterminethesmallestsetofcolorswithwhichwecanproperlycolortheinputgraph.Thisproblem isamongKarp’sfamouslistof21NP-completeproblems [16] andsinceitoftenarisesinpractice,heuristicstosolveitare deployed inawiderangeofapplications.Averynaturalsuchheuristicisthefollowing.Wegreedilyﬁndapropercoloring ofthegraph,andthentrytosuppressanyofitscolorsinthefollowingway:saywewanttosuppresscolorc.Ifthereisa vertex v that hasreceivedcolorc,andthereis anothercolorc

=

^c ^that ^does^not ^appearⁱⁿ^theneighborhoodof v,then wecansafelyrecolorthevertexv withcolorc withoutmakingthecoloringimproper.Weterminatethisprocessoncewe cannotsuppressanycoloranymore.

*

Correspondingauthors.

E-mailaddresses:lars.jaffke@uib.no(L. Jaffke),paloma.lima@uib.no(P.T. Lima).

1 SupportedbytheBergenResearchFoundation(BFS).

2 SupportedbyResearchCouncilofNorwayviatheproject“CLASSIS”,grantnumber249994.

https://doi.org/10.1016/j.tcs.2020.02.007

0304-3975/©²⁰²⁰^TheÂuthor(s).^Published^byÊlsevier^B.V.^Thisîsânôpenâccessârticleûnder^the^CC^BY^license (http://creativecommons.org/licenses/by/4.0/).

(2)

Topredicttheworst-casebehavioroftheaboveheuristic,IrvingandManlovedeﬁnedthenotionsofab-coloring andthe b-chromaticnumberofagraph [14].Ab-coloringofagraphG isapropercoloringsuch thatineverycolorclassthereisa vertexthathasaneighborinalloftheremainingcolorclasses,andtheb-chromaticnumberofG,denotedby

χ

b

(

G

)

,isthe maximumintegerksuchthatGadmitsab-coloringwithkcolors.Weobservethatinab-coloringwithkcolors,thereisno colorthatcanbesuppressedtoobtainapropercoloringwithk

−

^{1 colors,}^hence

χ

b

(

G

)

describestheworst-casebehavior ofthe previously described heuristic on thegraph G.We consider thefollowing two computational problemsassociated withb-coloringsofgraphs.

Input: GraphG,integerk

Question: DoesGadmitab-coloringwithkcolors?

b-Coloring

Input: GraphG,integerk Question: Is

χ

b

(

G

) ≥

^k?

b-Chromatic Number

Wewouldliketopointoutanimportantdistinctionfromthe‘standard’notionofpropercolorings ofgraphs:IfagraphG hasab-coloringwithkcolors,thenthisimpliesthat

χ

b

(

G

) ≥

^k.^However,^if

χ

b

(

G

) ≥

^k^then^we^canⁱⁿ^general^not^conclude that G hasa b-coloringwithk colors. Agraphforwhich thelatter implicationholdsaswell is calledb-continuous.This notionismostlyofstructuralinterest,sincetheproblemofdeterminingifagraphisb-continuous isNP-completeevenif anoptimalpropercoloringandab-coloringwith

χ

b

(

G

)

colorsaregiven [2].

Besides observing that

χ

b

(

G

) ≤ (

G

) +

^{1 where}

(

G

)

denotes the maximum degree of G, Irving andManlove [14]

deﬁned the m-degree of G as the largest integer i such that G has i vertices of degree at least i

−

^1. ^It ^follows ^that

χ

_b

(

G

) ≤

^m

(

G

)

;observealsothatm

(

G

) ≤ (

G

) +

^1.^Since^the^deﬁnition^of^theb-chromaticnumberoriginatedintheanalysis oftheworst-casebehaviorofgraphcoloringheuristics,graphswhoseb-chromaticnumberstakeoncriticalvalues,i.e.values that are close to theseupper bounds, are of special interest. In particular, identifying them can be helpful instructural investigationsconcerningtheperformanceofgraphcoloringheuristics.

Intermsofcomputationalcomplexity,IrvingandManloveshowedthatbothb-Coloringandb-ChromaticNumberare NP-complete [14] andSampaioobservedthat b-ColoringisNP-completeevenforeveryﬁxed integerk

≥

^{3 [19].} ^Panolan etal. [18] gaveanexact exponentialalgorithmforb-ChromaticNumberrunningintime O

(

3ⁿn⁴ logn

)

andanalgorithm that solves b-Coloring in time O(_n

k

2ⁿ⁻^kn⁴logn

)

. From the perspective of parameterized complexity [6,8], it has been shownthat b-ChromaticNumberis W

[

¹

]

^-hard parameterized by k [18] andthat the dual problemof deciding whether

χ

b

(

G

) ≥

ⁿ

−

^k,^whereⁿ^denotes^the^number^of^verticesⁱⁿ^G,^is^FPTparameterizedbyk[13].

Sincetheabove mentionedupperbounds

(

G

) +

^{1 and}^m

(

G

)

ontheb-chromaticnumberare trivialto compute,itis naturalto ask whetherthereexist eﬃcientalgorithms that decide whether

χ

b

(

G

) = (

G

) +

^{1 or}

χ

b

(

G

) =

^m

(

G

)

. Itturns outboththeseproblemsareNP-completeaswell [12,14,17].However,itisknownthattheproblemofdecidingwhethera graphGadmitsab-coloringwithk

= (

G

) +

^{1 colors}^is^FPTparameterizedbyk[18,19].

TheDichotomyResult.Oneofthemaincontributionsofthispaperisacomplexity dichotomyoftheb-Coloringproblem forﬁxedk,wheneverkisclosetoeither

(

G

) +

^{1 or}^m

(

G

)

.Inparticular,forﬁxedk

∈ {(

^G

) +

¹

−

^p

,

m

(

G

) −

^p

}

^,^we^show thattheproblemispolynomial-timesolvablewhenp

∈ {

⁰

,

1

}

^and,^evenⁱⁿ^the^case^k

=

^3,NP-completeforallﬁxed p

≥

^2.

More speciﬁcally, we give XPtime algorithms forthe casesk

=

^m

(

G

)

,k

= (

G

)

, andk

=

^m

(

G

) −

^{1 which} ^together ^with theFPTalgorithmforthecasek

= (

G

) +

1 [18,19] andtheaforementioned NP-hardnessresultfork

=

3 completesthe picture.Wenowformallystatethisresult.

Theorem1.LetG beagraph,p

∈

Nandk

∈ { (

G

) +

¹

−

^p

,

m

(

G

) −

^p

}

^.^The^problem^of^deciding^whether^{G has}^a^b-coloring^with^k colorsis

(i) NP-completeifk ispartoftheinputandp

∈ {

⁰

,

1

}

^, (ii) NP-completeifk

=

³^and^p

≥

^2,^and

(iii) polynomial-timesolvableforanyﬁxedpositivek andp

∈ {

⁰

,

1

}

^.

Maximum DegreeParameterizations. The positive results in our dichotomy theorem provide XP-algorithms to decide whethera graphhas a b-coloring witha number ofcolors that either preciselymeets or isonebelow one of two upper boundsontheb-chromaticnumber,theparameterbeingthenumberofcolorsineachofthecases.Towardsmore‘ﬂexible’

(parameterized)tractability results,we considerparameterizations oftheb-Coloringproblemthat involvethemaximum degree

(

G

)

of the input graph G, butask forthe existence ofb-colorings witha numberof colors that in generalis differentfrom

(

G

) +

^{1 or}

(

G

)

.

(3)

First,asanadditiontotheresultthatinFPTtimeparameterizedby

(

G

)

,one candecidewhetherG hasab-coloring with

(

G

) +

1 colors [18,19], we show that in thesame parameterizationwe can decide inFPT time whether G has a b-coloringwithm

(

G

)

colors.

Theorem2.LetG beagraph.TheproblemofdecidingwhetherG hasab-coloringwithm

(

G

)

colorsisFPTparameterizedby

(

G

)

. One of the cruciallyused facts inthe algorithm of theprevious theoremis that if we ask whethera graph G has a b-coloringwithk

=

^m

(

G

)

colors,then thenumberofverticesofdegreeatleastkisatmostk.We generalizethissetting andparameterizeb-Coloringbythemaximumdegreeplusthenumberofverticesofdegreeatleastk.Weshowthatthis problemisFPTaswell.

Theorem3.LetG beagraph.TheproblemofdecidingwhetherG hasab-coloringwithk colorsisFPTparameterizedby

(

G

) +

_k

(

G

)

, where

_k

(

G

)

denotesthenumberofverticesofdegreeatleastk inG.

We now argue that parameterizing by only one of the two invariants used in Theorem 3 is not suﬃcient to obtain eﬃcient parameterized algorithms. From the result of Kratochvíl et al. [17], statingthat b-Coloringis NP-complete for k

= (

G

) +

^1, ^it ^follows ^that ^b-^Coloring ^is NP-complete when

(

G

)

is unbounded and

_k

(

G

) =

^0. ^On ^the ^other ^hand, Theorem 1(ii) implies that b-Coloring is already NP-complete when k

=

^{3 and}

(

G

) =

^4. ^Together, ^this ^rules ^out ^the possibility ofFPT- andevenof XP-algorithms forparameterizationsby one ofthetwo parametersalone, unlessP

=

^NP.

Parameterizationsofgraphcoloring problemsbythenumberofhighdegree verticeshavepreviouslybeenconsidered for vertexcoloring [1] andedgecoloring [10].

AnextendedabstractofthisworkappearedintheproceedingsofMFCS2019 [15].

Organization.Therestofthepaperisorganizedasfollows.AftergivingpreliminarydeﬁnitionsinSection2,wepresentthe hardness resultsinSection 3,thealgorithmic resultsofthedichotomy inSection 4,andthe algorithmsforthemaximum degreeparameterizationsinSection5.WeconcludeinSection6.

2. Preliminaries

Weusethefollowingnotation:Fork

∈

N,

[

^k

] := {

¹

, . . . ,

k

}

^.^For^a^function ^f

:

^X

→

^Y ^and ^X

⊆

^X,^we^denote^by ^f

|

X the restriction of f to X andby f

(

X

)

theset

{

^f

(

x

) |

^x

∈

^X

}

^. ^Forâ^set ^X ândân înteger^n,^we ^denote^by _X

n

thesetofall size-nsubsetsof X.

Graphs.Throughoutthepapera graphG withvertexsetV

(

G

)

andedgeset E

(

G

) ⊆

_V₍_G₎

2

isﬁniteandsimple.Weoften denote anedge

{

^u

,

v

} ∈

^E

(

G

)

by theshorthand uv.Forgraphs G and H we denoteby H

⊆

^G ^that ^H îsâ^subgraph ôf^G, i.e. V

(

H

) ⊆

^V

(

G

)

and E

(

H

) ⊆

^E

(

G

)

. Weoften usethe notation n

:= |

^V

(

G

)|

^.^For^a ^vertex ^v

∈

^V

(

G

)

,we denote by N_G

(

v

)

the openneighborhoodof v in G,i.e. NG

(

v

) = {

^w

∈

^V

(

G

) |

^{v w}

∈

^E

(

G

) }

^,^and^by ^NG

[

^v

]

^the ^closedneighborhood of v in G, i.e.NG

[

^v

] := {

^v

} ∪

^NG

(

v

)

.Forasetofvertices X

⊆

^V

(

G

)

,weletNG

(

X

) :=

v∈^XNG

(

v

) \

^X ^and^NG

[

^X

] :=

^X

∪

^NG

(

X

)

.When Gisclearfromthecontext,weabbreviate‘NG’to‘N’.Thedegreeofavertexv

∈

^V

(

G

)

isthesizeofitsopenneighborhood, andwedenoteitbydeg_G

(

v

) := |

NG

(

v

)|

orsimplybydeg

(

v

)

ifGisclearfromthecontext.Foranintegerk,wedenoteby

k

(

G

)

thenumberofverticesofdegreeatleastkinG.Agraphisk-regularifallitsverticeshavedegreek.

Foravertexset X

⊆

^V

(

G

)

,wedenotebyG

[

^X

]

^the^subgraph^induced^by ^X,^i.e.^G

[

^X

] := (

X

,

E

(

G

) ∩

_X

2

)

.Wefurthermore let G

−

^X

:=

^G

[

^V

(

G

) \

^X

]

^be^the^subgraphôf^G ôbtained^from^removing^the^verticesⁱⁿ^X ând^forâ^single^vertex^x

∈

^V

(

G

)

, weusetheshorthand‘G

−

^x’^for^‘G

− {

^x

}

^’.

AgraphG issaidtobeconnectedifforany2-partition

(

X

,

Y

)

of V

(

G

)

,thereisanedgexy

∈

^E

(

G

)

suchthat x

∈

^X ^and y

∈

^Y, ^anddisconnected otherwise.Aconnectedcomponentof agraph G isa maximalconnectedsubgraph ofG.A pathis a connected graphofmaximum degree two,having preciselytwo vertices ofdegree one, calledits endpoints. The length of apath isits numberofedges. Givena graph G andtwo verticesu andv,thedistancebetween u andv,denotedby distG

(

u

,

v

)

(orsimplydist

(

u

,

v

)

ifG isclearfromthecontext),isthelengthoftheshortestpathinG thathasuandv as endpoints.

AgraphG isacompletegraphifeverypairofverticesofGisadjacent.AsetC

⊆

^V

(

G

)

isacliqueifG

[

^C

]

^is^a^complete graph. Aset S

⊆

^V

(

G

)

is an independentsetif G

[

^S

]

^has ^noêdges. Â ^graph ^G îsâ ^bipartite^graph îf îts ^vertex^set ^can^be partitioned into two independent sets. A bipartite graph with bipartition

(

A

,

B

)

is a completebipartitegraph if all pairs consistingofonevertexfrom A andonevertexfromB areadjacent,andwitha

= |

^A

|

^and^b

= |

^B

|

^,^we^denote^it^by ^Ka,b.A staristhegraph K₁_,_b,withb

≥

^2,ând^we^call^center^theûnique^vertexôf^degree^b ând^leaves^the^verticesôf^degreeône.

Colorings.GivenagraphG,amap

γ :

^V

(

G

) → [

^k

]

îs^calledâ^coloringôf^{G with}^{k colors.}Îf^forêvery^pairôfâdjacent^vertices, uv

∈

^E

(

G

)

,wehavethat

γ (

u

) = γ (

v

)

,thenthecoloring

γ

iscalledproper.Fori

∈ [

^k

]

^,^we^call^the^set^of^vertices^u

∈

^V

(

G

)

suchthat

γ (

u

) =

ⁱ ^the^color^classî.Îf^forâllⁱ

∈ [

^k

]

^,^there^exists^a^vertex^xi

∈

^V

(

G

)

suchthat

(4)

(i)

γ (

xi

) =

^i,^and

(ii) foreach j

∈ [

^k

] \ {

ⁱ

}

^,^there^is^a^neighbor ^y

∈

^NG

(

x_i

)

ofx_isuchthat

γ (

y

) =

^j,

then

γ

iscalledab-coloring ofG.Fori

∈ [

^k

]

^,^we^call^a^vertex^xi satisfyingtheabovetwoconditionsab-vertexforcolori.

ParameterizedComplexity.Let

beanalphabet.Aparameterizedproblemisaset

⊆

^∗

×

N.Aparameterizedproblem

is said to be ﬁxed-parametertractable,or contained inthe complexity class FPT,if there exists an algorithm that for each

(

x

,

k

) ∈

^∗

×

N decides whether

(

x

,

k

) ∈

in time f

(

k

) · |

^x

|

^c ^for ^some ^computable ^function ^f ând ^fixed înteger c

∈

N.Aparameterizedproblem

issaidtobe containedinthecomplexity classXPifthereisanalgorithmthatforall

(

x

,

k

) ∈

^∗

×

Ndecideswhether

(

x

,

k

) ∈

intime f

(

k

) · |

^x

|

^g⁽^k⁾^for^some^computable^functions ^f ^and^g.

Akernelizationalgorithmfora parameterizedproblem

⊆

^∗

×

N isapolynomial-timealgorithm thattakesasinput an instance

(

x

,

k

) ∈

^∗

×

N andeithercorrectlydecides whether

(

x

,

k

) ∈

oroutputsan instance

(

x

,

k

) ∈

^∗

×

N with _x

+

^k

≤

^f

(

k

)

forsomecomputablefunction f forwhich

(

x

,

k

) ∈

ifandonlyif

(

x

,

k

) ∈

.Wesaythat

admitsakernel ifthereisakernelizationalgorithmfor

.

3. Hardnessresults

Inthis section weprove the hardness resultsofour complexity dichotomy.First, we showthat b-ChromaticNumber andb-Coloring are NP-complete fork

=

^m

(

G

) −

¹

= (

G

)

, based on a reduction dueto Havet et al. [12] who showed NP-completenessforthecasek

=

^m

(

G

)

.

Theorem3.1.b-ChromaticNumberandb-ColoringareNP-complete,evenwhenk

=

^m

(

G

) −

¹

= (

G

)

.

Proof. Asintheproof ofHavetetal. [12],the reductionisfromthe NP-completeproblem3-EdgeColoringof3-regular graphs, whichtakes asinput a 3-regular graph G and askswhetherthe edges of G can be properly colored withthree colors.

Given an instance G of 3-EdgeColoring, an instance H of b-ChromaticNumber and b-Coloring is constructed as follows.Thegraph HhasonevertexforeachvertexofG,that wedenoteby v1

, . . . ,

vn,onevertexforeachedge,thatwe denotebyu1

, . . . ,

um andasetof4n

+

13 verticesthat wedenoteby S.Theedgesetof Hissuchthat H

[{

^v1

, . . . ,

vn

}]

^is aclique, H

[

^S

]

îs^the^disjointûnionôfône^copyôf^the^complete^bipartite^graph ^Kn,n+3 andtwocopiesofK₂_,_n₊₃ and v_iu_j is an edgeif theedge corresponding to u_j isincident to the vertexcorresponding to v_i in G. The constructedgraph H issuch that

(

H

) =

ⁿ

+

^{3 and} ^H ^hasⁿ

+

^{4 vertices}^of^degree ⁿ

+

^3,^which ^implies^that^m

(

H

) =

ⁿ

+

^4.^The ^difference^to theconstructionusedin [12] isthatinsteadofthethreecompletebipartitegraphsmentionedabove,theauthorsusethree copiesofthestarK₁_,_n₊₂.

Claim3.1.1.AconnectedcomponentofH thatisacompletebipartitegraphcancontainb-verticesofatmostonecolorin anyb-coloringof Hwithatleastn

+

^{3 colors.}

Proof. Consideracomponentof H thatinducesa Ki,n+³,withi

∈ {

²

,

n

}

^.^In^any^b-coloring^with^k

≥

ⁿ

+

^{3 colors,}^only^the verticesofdegreeatleastn

+

^2,^soⁱⁿ^this^case^the^vertices^of^degreeⁿ

+

^{3 can}^be^b-verticesⁱⁿ ^H.Îf^xîsâ^b-vertex^forâ givencolor,thentheremaining k

−

^{1 colors}âppearôn^the^verticesôf ^N

(

x

)

.We concludethatanyothervertexofdegree n

+

^{3 of}^this^component^will^be^assigned^the^same^color^as^x.

WeprovethatHhasab-coloringwithk

=

ⁿ

+

^{3 colors}îfândônlyîf^Gîsâ^Yes^-instance^for^3-Edge^Coloring^byûsing^the samestepsasintheproofofTheorem3of[12] andwiththeadditionaluseofClaim3.1.1.ThisprovestheNP-completeness ofb-Coloringwhenk

=

^m

(

G

) −

¹

= (

G

)

.Furthermore,weprovethat

χ

b

(

H

) ≥

ⁿ

+

^{3 if}ândônlyîf^H^hasâ^b-coloring^with n

+

^{3 colors.}^This^yields^the^analogous^result^for^b-^Chromatic^Number^.

First,assume that G isaYes-instancefor3-EdgeColoring.Let

γ

E

:

^E

(

G

) → [

³

]

^be ^a^proper ^3-edge^coloring^for^G.^We constructab-coloring

γ

H forH inthefollowingway.Foreach1

≤

ⁱ

≤ |

^E

(

G

) |

^,

γ

H

(

ui

) = γ

E

(

ei

)

andeach1

≤

^j

≤

^n,^we^let

γ

H

(

vj

) =

^j

+

^3. ^Note ^that ^since

γ

E is a 3-edgecoloring for G, thevertices v1

, . . . ,

vn in H are b-verticesfor thecolors 4

, . . . ,

n

+

^3:Âny^vertexⁱⁿ^Gîsîncident^with^{3 edges}^since^Gîs^3-regular,ând^since

γ

E isproper,eachsuchedgereceivesa differentcolor.Hence,foranyvertexv_i,thecolors

{

¹

,

2

,

3

}

^appear^on^NH

(

v_i

) ∩ {

^u1

, . . . ,

u_|_E₍_G_)|

}

^.^Now^we^can^color^the^rest ofthegraphHinsuchawaythateachconnectedcomponentthatisacompletebipartitegraphcontainsab-vertexforone ofthethreeremainingcolors.

Nowweconsidertheotherdirection.WestartbyobservingthatClaim3.1.1impliesthat H doesnotadmitab-coloring withn

+

⁴

=

^m

(

H

) = (

H

) +

^{1 colors,}^since^the^set^of^vertices^of^degreeⁿ

+

^{3 can}^contain^b-vertices^for^at^most^three^colors inanysuchab-coloring.Thisimpliesthat

χ

b

(

H

) ≥

^m

(

H

) −

¹

= (

H

)

ifandonlyifHhasab-coloringwithm

(

H

) −

¹

= (

H

)

colors.

Assume H hasab-coloring

γ

H withn

+

^{3 colors.} ^Since^by ^Claim^3.1.1 ^the^set ^S ^contains ^b-vertices^for^at^most^three colors,wehavethattheverticesv1

, . . . ,

vn areb-verticesinthiscoloring.Moreover, sincetheyinduceacliqueinH,they

(5)

allhavedistinctcolors.Assume,withoutlossofgenerality,that

γ

H

( {

^v1

, . . . ,

vn

} ) = {

⁴

, . . . ,

n

+

³

}

^.^This^implies^that^for^each i,

γ

H

(

N

(

vi

) ∩ {

^u1

, . . . ,

u_|E(G)|

} ) = {

¹

,

2

,

3

}

^.^It^follows^that

γ

E

:

^E

(

G

) →

N,deﬁnedas

γ

E

(

ei

) = γ

H

(

ui

)

,fori

∈ {

¹

, . . . , |

E

(

G

)|}

, is a 3-edgecoloring of G.We arguethat

γ

E isproper. Suppose fora contradictionthat thereexist adjacentedge e_i and e_j,sharingtheendpoint v_s,such that

γ

E

(

e_i

) = γ

E

(

e_j

) =

^c.^Since^degG

(

v_s

) =

^3,ând^two ôfîtsîncident êdges^received ^the samecolorc,we canconcludethatatleastoneofthecolors

{

¹

,

2

,

3

}

^does^not ^appearⁱⁿ^theneighborhoodof v_s in H,a contradictionwiththefactthatv_sisab-vertexofitscolorin

γ

H.

Theprevioustheorem,togetherwiththeresultthatb-ColoringisNP-completewhenk

= (

G

) +

^{1 [17] and}^when^k

=

m

(

G

)

[12], proves Theorem 1(i). We now turnto the proof of Theorem1(ii), that is, we show that b-Coloringremains NP-completefork

=

^{3 if}^k

= (

G

) +

¹

−

^p^or^k

=

^m

(

G

) −

^p^for^any ^p

≥

^2,^basedônâ^reduction^due^toSampaio [19].Note thatthefollowingpropositionindeedprovesTheorem1(ii) asforfixed p

≥

^2,^we^have^that³

∈ {(

^G

) +

¹

−

^p

,

m

(

G

) −

^p

}

^if andonlyif

(

G

) =

^p

+

^{2 or}^m

(

G

) =

^p

+

^3.

Proposition3.2.Foreveryﬁxedintegerp

≥

^2,^the^problemôf^deciding^whetherâ^graph^{G has}â^b-coloring^with³^colorsîs^NP- completewhen

(

G

) =

^p

+

²^or^m

(

G

) =

^p

+

^3.

Proof. SampaioshowedthattheproblemofdecidingwhetheragraphG hasab-coloringwithkcolorsisNP-completefor anyﬁxedk

∈

N [19,Proposition4.5.1].Forthecaseofk

=

^3,^the^reduction^is^{from 3}^-Coloring^on^planar ^4-regular^graphs whichisknowntobe NP-complete [11].Inthisreduction,onetakesthegraphofthe 3-Coloringinstanceandaddsthree starswithtwoleaveseachtothegraphwhichcanserveastheb-verticesintheresultinginstanceofb-Coloring.Sincethis doesnotincreasethemaximumdegree,weimmediatelyhavethattheproblemofdecidingwhetheragraphofmaximum degree 4 has a b-coloringwith3 colors isNP-complete.Inother words, thisproves NP-completenessof thequestion of whether a graph G with maximumdegree p

+

^{2 admits} ^a ^b-coloring ^with^{3 colors} ⁱⁿ ^the ^case ^p

=

^2. Furthermore, by addingmoreleavestooneofthestarsandtherebyincreasingthemaximumdegreeofthegraphintheresultinginstance, we havethatforanyﬁxedinteger p

≥

^2,^it^isNP-completetodecidewhethera graphofmaximumdegree

(

G

) =

^p

+

² hasab-coloringwiththreecolors.

Towardsthestatement regardingm

(

G

)

,weﬁrstobservethat fora 4-regulargraphG on atleastﬁvevertices,wehave thatm

(

G

) =

^5.^Weôbserve^thatⁱⁿâny^star^withât^least^two^leaves,^the^center^vertex^can^beâ^b-vertexⁱⁿâ^coloring^with³ colors.WeconstructagraphGbyaddingfivestarswithfourleaveseachtoG,andweagainhavethat G hasa3-coloring ifandonlyifG hasab-coloringwith3 colors,showingthat theproblemofdecidingwhethera graphH withm

(

H

) =

⁵ hasa b-coloring with3 colors,is NP-complete.Inother words,itisNP-completetodecideifagraph H hasab-coloring withm

(

H

) =

^p

+

^{3 has}^a^b-coloring^with^{3 colors}ⁱⁿ^the^case^p

=

^2.^Note^thatⁱⁿ^this^reduction,^the^center^vertices^of^the starscanberegardedastheverticesdeterminingthem-degreeofthegraphintheresultinginstanceofb-coloringwith3 colors,sowecanextendthisresultinasimilarwayasabove.Thatis,foranyp

≥

^2,^given^a^4-regular^graph^G,^we^can^add p

+

^{3 stars}^with^p

+

^{2 leaves}^each^to^G,^implying^that^for^the^resulting^graph^G^,^m

(

G

) =

^p

+

^3.^Again, ^G^has^a^3-coloring ifandonlyifGhasab-coloringwith3 colors,implyingthesecondstatementoftheproposition.

Weconcludethissectionbyconsideringthecomplexityofthetwoproblemsongraphswithfewverticesofhighdegree.

Sinceb-ChromaticNumberandb-ColoringareknowntobeNP-completewhenk

= (

G

) +

^{1 [17],}^we^make^the^following observationwhichisofrelevancetoussinceinSection5.2,weshowthatb-ColoringisFPTparameterizedby

(

G

) +

k

(

G

)

.

Observation3.3.b-ChromaticNumberandb-ColoringareNP-completeongraphswith

k

(

G

) =

^0,^where^{k is}^the^integer^associ- atedwiththerespectiveproblem.

4. Dichotomyalgorithms

In thissectionwe give thealgorithms inourdichotomy result, provingTheorem 1(iii). Weshow thatforﬁxed k

∈

N, theproblemofdecidingwhetheragraphG admitsab-coloringwithkcolorsispolynomial-timesolvablewhenk

=

^m

(

G

)

(Section4.2),whenk

= (

G

)

(Section4.3),andwhenk

=

^m

(

G

) −

^{1 (Section}^4.4),^by^providingXP-algorithmsforeachcase.

Anaturalwayofsolvingtheb-Coloringproblemistotrytoidentifyasetofk b-vertices,andforeachvertexintheseta setofk

−

1 neighborsthatcanbeusedtomakeavertexab-vertexforitscolor,andthenextendtheresultingcoloringto theremainder ofthegraph.Weguessallsuchsetsandcolorings,andshowthattheproblemofdecidingwhetheragiven coloringcanbe extendedtoapropercoloringoftheremainderofthegraphissolvableinpolynomialtimeineachofthe abovecases.

The strategy of identifying the set of b-vertices andsubsets of their neighbors that make them b-vertices was (for instance) alsoused to give polynomial-timealgorithms tocompute theb-chromatic number oftrees [14] andof graphs withlargegirth [4].Wecaptureitbydeﬁningthenotionofab-precoloringinthenextsubsection.

(6)

4.1. b-precolorings

Allalgorithmsinthissectionarebasedonguessingapropercoloringofseveralverticesinthegraph,forwhichwenow introducethenecessaryterminologyandestablishsomepreliminaryresults.

Deﬁnition4.1(Precoloring).LetGbeagraphandk

∈

N.AprecoloringwithkcolorsofagraphGisanassignmentofcolors toasubsetofitsvertices,i.e.for X

⊆

^V

(

G

)

,itisamap

γ

X

:

^X

→ [

^k

]

^.^We^call

γ

X proper,ifitisapropercoloringofG

[

^X

]

^. Wesaythatacoloring

γ :

^V

(

G

) → [

^k

]

^extends

γ

X,if

γ |

X

= γ

X.

Weusethefollowingnotation.Fortwoprecolorings

γ

X and

γ

Y with X

∩

^Y

= ∅

^,^we ^denote^by

γ

X

∪ γ

Y theprecoloring that colors thevertices in X accordingto

γ

X andthevertices in Y accordingto Y, i.e.theprecoloring

γ

X∪^Y

:= γ

X

∪ γ

Y deﬁnedas:

γ

X∪^Y

(

v

) =

γ

X

(

v

),

ifv

∈

^X

γ

Y

(

v

),

ifv

∈

Y for allv

∈

^X

∪

^Y

Next,wedeﬁneaspecialtypeofprecoloringwiththepropertythatanypropercoloringthat extendsitisa b-coloring ofthegraph.

Deﬁnition4.2(b-precoloring).Let G be agraph,k

∈

N, X

⊆

^V

(

G

)

and

γ

X a precoloring.We call

γ

X ab-precoloringwithk colorsif

γ

X isab-coloringofG

[

^X

]

^.^Ab-precoloring

γ

X iscalledminimalifforanyY

⊂

^X^,

γ

X

|

Y isnotab-precoloring.

Itisimmediatethatanyb-coloringcanbeobtainedbyextendingaminimalb-precoloring,afactthatwecaptureinthe followingobservation.

Observation4.3.LetG beagraph,k

∈

N,and

γ

ab-coloringofG withk colors.Then,thereisasetX

⊆

^V

(

G

)

suchthat

γ _|

X isa minimalb-precoloring.

Thenext observationcapturesthestructureofminimalb-precoloringswithk colors.Roughlyspeaking,each suchpre- coloring onlycolors aset ofk b-verticesandforeach b-vertex a setofk

−

^{1 of} ^its ^neighbors^that ^make^that ^vertex^the b-vertex ofitscolor.We willusethispropertyinthe enumerationalgorithminthissection toguaranteethat we indeed enumerateallminimalb-precoloringswithagivennumberofcolors.

Observation4.4.Let

γ

Xbeaminimalb-precoloringwithk colors.Then,X

=

^B

∪

^{Z ,}^where (i) B

= {

^x1

, . . . ,

xk

}

^and^forⁱ

∈ [

^k

]

^,

γ

X

(

xi

) =

^i,^and

(ii) Z

=

i∈[^k]Z_i,whereZ_i

∈

_N₍_x_i₎

k−¹

and

γ

X

(

Z_i

) = [

^k

] \ {

ⁱ

}

^.

Wearenowreadytogivetheenumerationalgorithmforminimalb-precolorings.

Lemma4.5.LetG beagraphonn verticesandk

∈

N.Thenumberofminimalb-precoloringswithk colorsofG isatmost

β(

k

) :=

ⁿ^k

·

^k⁽^k⁻¹⁾

· (

k

−

¹

) !

^k

,

(1)

where

:= (

G

)

andtheycanbeenumeratedintime

β(

k

) ·

^k^O⁽¹⁾^.

Proof. ByObservation4.4,anyminimalb-precoloringonlycolorsasetofk b-vertices,andforeachofthemasize-

(

k

−

¹

)

subsetofitsneighborsthatarecoloredbijectivelywiththeremainingcolors.

To guessall b-verticesin G,we enumerateall ordered vertex sets of size k, let

{

^x1

, . . . ,

xk

}

^be ^such ^a ^set.^Next, ^we enumerate all size-

(

k

−

¹

)

subsets ofneighbors of each x_i that can make x_i theb-vertex ofcolor i. Let

(

Z₁

, . . . ,

Z_k

)

be a tupleofsuch setsofneighbors.Then we enumerateforeach i

∈ [

^k

]

^,^all ^bijective^colorings ^of

π

i

:

^Zi

→ [

^k

] \ {

ⁱ

}

^– ^these areprecisely thecoloringsof Zi thatcanmake xi theb-vertexforcolori.Givensucha tuple

( π

1

, . . . , π

k

)

,we makesure thatitisconsistent:foreachi

,

j

∈ [

^k

]

^and^each^vertex^v

∈

^Zi

∩

^Zj,weensurethat

π

i and

π

j assign v thesamecolor,i.e.

π

i

(

v

) = π

j

(

v

)

; similarly, ifx_i

∈

^Zj,then we ensurethat

π

j

(

x_i

) =

ⁱ ^(recall^that ^xi is supposed tobe theb-vertex of color i).Ifso,weconstructa precoloring

γ

B∪^Z accordingtoourchoiceof B

= {

^x1

, . . . ,

x_k

}

^and

( π

1

, . . . π

_k

)

andifitisaminimal b-precoloringweoutputit.WegivethedetailsinAlgorithm1.

Wenowshowthatthealgorithmiscorrect.

Claim4.5.1.Aprecoloring

γ

X isaminimalb-precoloringwithkcolorsifandonlyifAlgorithm1returnsitinline8insome iteration.

(7)

Input :AgraphG,apositiveintegerk.

Output:Allminimalb-precoloringswithkcolorsofG

1 foreachB

∈

_V₍_G₎

k

andeveryorderingx₁

, . . . ,

x_koftheelementsofBdo

2 foreach

(

Z1

, . . . ,

Z_k

) ∈

_N₍_x₁₎

k−¹

× · · · ×

_N₍_x_k₎

k−¹

do

3 foreach

( π

1

, . . . , π

k

)

,

(i) whereforalli

∈ [

^k

]

^,

π

i

:

^Zi

→ [

^k

] \ {

ⁱ

}

^is^a^bijection, (ii) foralli

,

j

∈ [

^k

]

^and^all^v

∈

^Zi

∩

^Zj,

π

i

(

v

) = π

j

(

v

)

,and (iii) foralli

,

j

∈ [

^k

]

^,^if^xi

∈

^Zj,then

π

j

(

xi

) =

ⁱ

4 do

5 LetZ

:= ∪

i∈[^k]Z_iand

γ

B∪Z

:

^B

∪

^Z

→ [

^k

]

^;

6 fori

∈ [

^k

]

^do

γ

B∪^Z

(

xi

) :=

^i;

7 fori

∈ [

^k

]

^and^v

∈

^Zido

γ

B∪^Z

(

v

) := π

i

(

v

)

;

8 if

γ

B∪Zisaminimalb-precoloringthen output

γ

B∪Z andcontinue;

Algorithm 1:Enumerating all minimalb-precolorings withkcolors of a graph.

Proof. SupposeAlgorithm1returnsaprecoloring

γ

X.Weﬁrstarguethat

γ

X iswell-deﬁned.Let X

=

^B

∪

^Z ^following^the notation ofAlgorithm1.Itisimmediatethat

γ

X

|

B iswell-deﬁned.Fortheremainingverticesv

∈

^Z,^we^verify^as^condition (ii) inline3 thatwhenever v

∈

^Zi

∩

^Zj,

π

i

(

v

) = π

j

(

v

)

.Moreover, condition (iii) inline3ensures that whenever xi

∈

^Zj, then

π

j

(

xi

) =

^i.^Hence^if^the^tuple

( π

1

, . . . , π

k

)

passesthecheckinline3,thenforeachvertexv

∈

^Z ^there^is^precisely^one color that

γ

X assigns to v inline7, andif v

∈

^Zj

∩

^B,^then

π

j assigns v acolor that isconsistent withline 6. We can concludethat

γ

X iswell-deﬁned.Bythecheckperformedinline8,wecanconcludethat

γ

X isaminimalb-precoloring.

NowsupposethatGcontainsaminimalb-precoloring

γ

X.ByObservation4.4,X consistsofan(ordered)setofb-vertices B

= {

^x1

, . . . ,

xk

}

^with

γ

X

(

xi

) =

ⁱ ^forⁱ

∈ [

^k

]

^,ândâ^set ^Z ^that^contains,^forêach^xi,asetofk

−

1 neighborsZi

⊆

^Z ^such^that

γ

X

(

Z_i

) = [

^k

] \ {

ⁱ

}

^.^SinceÂlgorithm¹ênumeratesâll ^such^possible^setsⁱⁿ^lines ¹ând^2,^we ^have^thatⁱⁿ^some îteration,ît guessed B

∪

^Z âs^the^setôf^vertices ^to^color.^Since ^theâlgorithmênumerates âllcombinationsof possibilitiesofcoloring the sets Zi bijectively withcolors

[

^k

] \ {

ⁱ

}

ⁱⁿ^line ^3, ît ^guessed â ^tupleôf ^bijections

( π

1

, . . . , π

k

)

from whichwe obtain

γ

X.Clearlywe havethatinthat case,

( π

1

, . . . , π

k

)

passesthecheck inline3andbyassumption,

γ

X passesthecheck in line8.

It remainstoargueits runtime.Inline1,thereare_n

k

choicesfortheset B andk

!

^choices^for^its^orderings, ⁱⁿ^line^2, thereareatmost

k−¹

k

choicesofk-tuplesofsize-

(

k

−

¹

)

setsofneighbors,andinline3,weenumerate

(

k

−

¹

) !

^k^k-tuples of bijectionsof setsof sizek

−

^1. ^The^remaining ^steps ^can ^be^executed ⁱⁿ ^time^k^O⁽¹⁾^: ^Byconstruction,

|

^B

∪

^Z

| ≤

^k²^,^and every colorhas a b-vertex. It remains to verify whetherthe coloring

γ

B∪Z is proper on G

[

^B

∪

^Z

]

^to ^conclude ^that ^it ^is a b-precoloring. Ifso, we can verifyminimality in polynomial time by simplytrying foreach vertex x

∈

^B

∪

^Z^,^whether

γ

B∪^Z\{^x}isstillab-precoloring.Ifwecanﬁndsuchavertexx,then

γ

B∪^Z isnotminimal,otherwiseitis.Thetotalruntime amountsto

n k

k

! ·

k

−

¹

k

· (

k

−

¹

) !

^k

·

^k^O(¹⁾

≤

ⁿ^k

·

^k⁽^k⁻¹⁾

· (

k

−

¹

) !

^k

·

^k^O(¹⁾

= β(

k

) ·

^k^O(¹⁾

,

asclaimed.Theupperboundof

β(

k

)

onthenumberofb-precoloringswithkcolorsfollowssincethek^O⁽¹⁾factorintherun- timeonlyconcernstheconstructionoftheprecoloringsandtheveriﬁcationofwhethertheyareindeedb-precolorings.

4.2. Algorithmfork

=

^m

(

G

)

OurﬁrstapplicationofLemma4.5istosolvetheb-Coloringprobleminthecasewhenk

=

^m

(

G

)

intimeXPparame- terizedbyk.Itturnsoutthat inthiscase,we aredealingwithaYes-instanceassoonaswe foundab-precoloringinthe inputgraphthatalsocolorsallhigh-degreevertices(seeClaim4.6.1).

Theorem4.6.LetG beagraph.ThereisanalgorithmthatdecideswhetherG hasab-coloringwithk

=

^m

(

G

)

colorsintimen^k²

·

2^O⁽^k²^logk⁾.

Proof. Let D

⊆

^V

(

G

)

denotethe setofverticesin G that havedegreeatleastk.Notethat by thedeﬁnitionofm

(

G

)

,we havethat

|

^D

| ≤

^k.

Claim4.6.1. Ghasab-coloringwithkcolorsifandonlyifG hasab-precoloring

γ

X suchthat D

⊆

^X ^and^there^exists^S

⊆

^D suchthat

γ

X

|

(X\^S)isaminimalb-precoloring.