b-Chromatic Number of Graphs
Lars Jaffke
Department of Informatics, University of Bergen, Norway lars.jaffke@uib.no
Paloma T. Lima
Department of Informatics, University of Bergen, Norway paloma.lima@uib.no
Abstract
Ab-coloringof a graphGis a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. Theb-Coloringproblem asks whether a graphGhas ab-coloring withkcolors. Theb-chromatic numberof a graphG, denoted byχb(G), is the maximum numberksuch thatGadmits ab-coloring withk colors. We consider the complexity of theb-Coloringproblem, whenever the value ofkis close to one of two upper bounds onχb(G): The maximum degree ∆(G) plus one, and them-degree, denoted bym(G), which is defined as the maximum numberisuch thatGhasivertices of degree at leasti−1. We obtain a dichotomy result for all fixedk∈Nwhenkis close to one of the two above mentioned upper bounds.
Concretely, we show that ifk∈ {∆(G) + 1−p, m(G)−p}, the problem is polynomial-time solvable wheneverp∈ {0,1} and, even whenk= 3, it isNP-complete wheneverp≥2. We furthermore consider parameterizations of theb-Coloringproblem that involve the maximum degree ∆(G) of the input graphGand give twoFPT-algorithms. First, we show that deciding whether a graphG has ab-coloring withm(G) colors isFPTparameterized by ∆(G). Second, we show thatb-Coloring isFPTparameterized by ∆(G) +`k(G), where`k(G) denotes the number of vertices of degree at leastk.
2012 ACM Subject Classification Mathematics of computing→Graph coloring Keywords and phrases b-Coloring,b-Chromatic Number
Digital Object Identifier 10.4230/LIPIcs.MFCS.2019.34
Related Version A full version is available at: https://arxiv.org/abs/1811.03966[13].
Funding Lars Jaffke: Supported by The Bergen Research Foundation (BFS).
Paloma T. Lima: Supported by Research Council of Norway via the project “CLASSIS”.
Acknowledgements We would like to thank Fedor Fomin for useful advice with good timing and Petr Golovach for pointing out the reference [7].
1 Introduction
Given a set of colors, aproper coloringof a graph is an assignment of a color to each of its vertices in such a way that no pair of adjacent vertices receive the same color. In the deeply studiedGraph Coloringproblem, we are given a graph and the question is to determine the smallest set of colors with which we can properly color the input graph. This problem is among Karp’s famous list of 21 NP-complete problems [14] and since it often arises in practice, heuristics to solve it are deployed in a wide range of applications. A very natural such heuristic is the following. We greedily find a proper coloring of the graph, and then try tosuppress any of its colors in the following way: say we want to suppress colorc. If there is a vertexv that has received colorc, and there is another colorc06=cthat does not appear in the neighborhood ofv, then we can safely recolor the vertexvwith colorc0 without
© Lars Jaffke and Paloma T. Lima;
making the coloring improper. We terminate this process once we cannot suppress any color anymore.
To predict the worst-case behavior of the above heuristic, Irving and Manlove defined the notions of ab-coloring and theb-chromatic number of a graph [12]. Ab-coloring of a graph Gis a proper coloring such that in every color class there is a vertex that has a neighbor in all of the remaining color classes, and theb-chromatic number ofG, denoted byχb(G), is the maximum integerksuch thatGadmits ab-coloring withk colors. We observe that in a b-coloring withkcolors, there is no color that can be suppressed to obtain a proper coloring withk−1 colors, henceχb(G) describes the worst-case behavior of the previously described heuristic on the graphG. We consider the following two computational problems associated withb-colorings of graphs.
Input: GraphG, integerk
Question: DoesGadmit ab-coloring withkcolors?
b-Coloring
Input: GraphG, integerk Question: Isχb(G)≥k?
b-Chromatic Number
We would like to point out an important distinction from the “standard” notion of proper colorings of graphs: If a graph G has a b-coloring with k colors, then this implies that χb(G) ≥ k. However, if χb(G) ≥ k then we can in general not conclude that G has a b-coloring with k colors. A graph for which the latter implication holds as well is called b-continuous. This notion is mostly of structural interest, since the problem of determining if a graph isb-continous isNP-complete even if an optimal proper coloring and ab-coloring withχb(G) colors are given [2].
Besides observing thatχb(G)≤∆(G) + 1 where ∆(G) denotes the maximum degree ofG, Irving and Manlove [12] defined them-degree ofGas the largest integerisuch that Ghas i vertices of degree at leasti−1. It follows thatχb(G)≤m(G). Since the definition of the b-chromatic number originated in the analysis of the worst-case behavior of graph coloring heuristics, graphs whose b-chromatic numbers take oncritical values, i.e. values that are close to these upper bounds, are of special interest. In particular, identifying them can be helpful in structural investigations concerning the performance of graph coloring heuristics.
In terms of computational complexity, Irving and Manlove showed that bothb-Coloring andb-Chromatic NumberareNP-complete [12] and Sampaio observed thatb-Coloring is NP-complete even for every fixed integerk ≥3 [17]. Panolan et al. [16] gave an exact exponential algorithm forb-Chromatic Number running in timeO(3nn4 logn) and an algorithm that solves b-Coloring in time O( nk
2n−kn4logn). From the perspective of parameterized complexity [6, 8], it has been shown thatb-Chromatic Number isW[1]-hard parameterized byk[16] and that the dual problem of deciding whetherχb(G)≥n−k, where ndenotes the number of vertices inG, isFPTparameterized byk [11].
Since the above mentioned upper bounds ∆(G) + 1 andm(G) on theb-chromatic number are trivial to compute, it is natural to ask whether there exist efficient algorithms that decide whetherχb(G) = ∆(G) + 1 orχb(G) =m(G). It turns out both these problems are NP-complete as well [10, 12, 15]. However, it is known that the problem of deciding whether a graphGadmits ab-coloring withk= ∆(G) + 1 colors isFPT parameterized byk[16, 17].
The Dichotomy Result. One of the main contributions of this paper is a complexity dichotomy of theb-Coloring problem for fixedk, wheneverkis close to either ∆(G) + 1 or m(G). In particular, for fixedk∈ {∆(G) + 1−p, m(G)−p}, we show that the problem is polynomial-time solvable whenp∈ {0,1}and, even in the case k= 3,NP-complete for all fixedp≥2. More specifically, we giveXPtime algorithms for the casesk=m(G),k= ∆(G), andk=m(G)−1 which together with theFPTalgorithm for the casek= ∆(G) + 1 [16, 17]
and the aforementionedNP-hardness result fork= 3 complete the picture. We now formally state this result.
ITheorem 1. LetGbe a graph,p∈Nand k∈ {∆(G) + 1−p, m(G)−p}. The problem of deciding whether Ghas ab-coloring withk colors is
(i) NP-complete ifk is part of the input andp∈ {0,1}, (ii) NP-complete ifk= 3andp≥2, and
(iii) polynomial-time solvable for any fixed positivekandp∈ {0,1}.
Maximum Degree Parameterizations. The positive results in our dichotomy theorem provideXP-algorithms to decide whether a graph has ab-coloring with a number of colors that either precisely meets or is one below one of two upper bounds on the b-chromatic number, with the parameter being the number of colors in each of the cases. Towards more
“flexible” tractability results, we consider parameterized versions ofb-Coloringthat involve the maximum degree ∆(G) of the input graph G, but ask for the existence ofb-colorings with a number of colors that in general is different from ∆(G) + 1 or ∆(G).
ITheorem 2. LetGbe a graph. The problem of deciding whether Ghas a b-coloring with m(G)colors isFPTparameterized by ∆(G).
One of the crucially used facts in the algorithm of the previous theorem is that if we ask whether a graphGhas ab-coloring withk=m(G) colors, then the number of vertices of degree at leastkis at mostk. We generalize this setting and parameterizeb-Coloringby the maximum degree plus the number of vertices of degree at leastk.
ITheorem 3. LetGbe a graph. The problem of deciding whether Ghas a b-coloring with k colors isFPTparameterized by∆(G) +`k(G), where `k(G)denotes the number of vertices of degree at leastkin G.
We now argue that parameterizing by only one of the two invariants used in Theorem 3 is not sufficient to obtain efficient parameterized algorithms. From the result of Kratochvíl et al. [15], stating thatb-ColoringisNP-complete fork= ∆(G)+1, it follows thatb-Coloring isNP-complete when ∆(G) is unbounded and`k(G) = 0. On the other hand, Theorem 1(ii) implies thatb-Coloringis alreadyNP-complete whenk= 3 and ∆(G) = 4. Together, this rules out the possibility ofFPT- and even ofXP-algorithms for parameterizations by one of the two parameters alone, unlessP=NP.
Parameterizations of graph coloring problems by the number of high degree vertices have previously been considered for vertex coloring [1] and edge coloring [9]. Throughout the text, proofs of statements marked with “♣” are deferred to the full version [13].
2 Preliminaries
We use the following notation: Fork∈N, [k]..={1, . . . , k}. For a functionf:X →Y and X0⊆X, we denote byf|X0 the restriction off toX0 and byf(X0) the set{f(x)|x∈X0}.
For a setX and an integern, we denote by Xn
the set of all size-nsubsets ofX.
Graphs. Throughout the paper a graphGwith vertex setV(G) and edge setE(G)⊆ V(G)2 is finite and simple. We often denote an edge {u, v} ∈ E(G) by the shorthanduv. For graphsGandH we denote byH ⊆GthatH is a subgraph of G, i.e. V(H)⊆V(G) and E(H)⊆E(G). We often use the notationn..=|V(G)|. For a vertex v∈V(G), we denote byNG(v) theopen neighborhood ofv inG, i.e.NG(v) ={w∈V(G)|vw∈E(G)}, and by NG[v] theclosed neighborhood of v inG, i.e. NG[v] ..={v} ∪NG(v). For a set of vertices X⊆V(G), we letNG(X)..=S
v∈XNG(v)\X andNG[X]..=X∪NG(X). WhenGis clear from the context, we abbreviate “NG” to “N”. Thedegreeof a vertex v∈V(G) is the size of its open neighborhood, and we denote it by degG(v)..=|NG(v)|or simply by deg(v) ifG is clear from the context. For an integerk, we denote by`k(G) the number of vertices of degree at leastk inG.
For a vertex setX ⊆V(G), we denote byG[X] the subgraphinduced byX, i.e.G[X]..= (X, E(G)∩ X2
). We furthermore letG−X..=G[V(G)\X] be the subgraph ofGobtained from removing the vertices inX and for a single vertexx∈V(G), we use the shorthand
“G−x” for “G− {x}”.
A graph G is said to be connected if for any 2-partition (X, Y) of V(G), there is an edgexy ∈E(G) such that x ∈X and y ∈ Y, and disconnected otherwise. A connected component of a graphGis a maximal connected subgraph ofG. Apathis a connected graph of maximum degree two, having precisely two vertices of degree one, called itsendpoints.
Thelength of a path is its number of edges. Given a graphGand two verticesuandv, the distance betweenuandv, denoted bydistG(u, v) (or simplydist(u, v) ifGis clear from the
context), is the length of the shortest path inGthat hasuandv as endpoints.
A graphGis a complete graph if every pair of vertices ofGis adjacent. A setC⊆V(G) is aclique ifG[C] is a complete graph. A setS⊆V(G) is anindependent set ifG[S] has no edges. A graphGis abipartite graphif its vertex set can be partitioned into two independent sets. A bipartite graph with bipartition (A, B) is a complete bipartite graph if all pairs consisting of one vertex fromAand one vertex fromB are adjacent, and witha=|A|and b=|B|, we denote it byKa,b. Astar is the graphK1,b, withb≥2, and we callcenter the unique vertex of degreebandleaves the vertices of degree one.
Colorings. Given a graphG, a mapγ:V(G)→[k] is called acoloring of Gwith k colors.
If for every pair of adjacent vertices,uv∈E(G), we have thatγ(u)6=γ(v), then the coloring γis calledproper. Fori∈[k], we call the set of verticesu∈V(G) such thatγ(u) =i the color class i. If for all i∈[k], there exists a vertexxi∈V(G) such that
(i) γ(xi) =i, and
(ii) for eachj ∈[k]\ {i}, there is a neighbor y∈NG(xi) ofxi such thatγ(y) =j,
thenγ is called ab-coloring ofG. For i∈[k], we call a vertexxi satisfying the above two conditions ab-vertex for colori.
Parameterized Complexity. Let Σ be an alphabet. A parameterized problem is a set Π⊆Σ∗×N. A parameterized problem Π is said to befixed-parameter tractable, or contained in the complexity classFPT, if there exists an algorithm that for each (x, k)∈Σ∗×Ndecides whether (x, k)∈Π in timef(k)· |x|c for some computable functionf and fixed integerc∈N. A parameterized problem Π is said to be contained in the complexity classXPif there is an algorithm that for all (x, k)∈Σ∗×Ndecides whether (x, k)∈Π in timef(k)·ng(k)for some computable functionsf andg.
Akernelization algorithm for a parameterized problem Π⊆Σ∗×Nis a polynomial-time algorithm that takes as input an instance (x, k)∈Σ∗×Nand either correctly decides whether
(x, k)∈Π or outputs an instance (x0, k0)∈Σ∗×Nwith|x0|+k0 ≤f(k) for some computable functionf for which (x, k)∈Π if and only if (x0, k0)∈Π. We say that Πadmits a kernel if there is a kernelization algorithm for Π.
3 Hardness Results
In this section we prove the hardness results of our complexity dichotomy. First, we show that b-Chromatic Numberandb-ColoringareNP-complete fork=m(G)−1 = ∆(G), based on a reduction for the casek=m(G) due to Havet et al. [10].
ITheorem 4(♣). b-Chromatic Numberandb-ColoringareNP-complete, even when k=m(G)−1 = ∆(G).
The previous theorem, together with the result thatb-ColoringisNP-complete whenk=
∆(G) + 1 [15] and when k=m(G) [10], proves Theorem 1(i). We now turn to the proof of Theorem 1(ii), that is, we show that b-Coloring remains NP-complete for k = 3 if k= ∆(G) + 1−pork=m(G)−pfor anyp≥2, based on a reduction due to Sampaio [17].
Note that the following proposition indeed proves Theorem 1(ii) as for fixedp≥2, we have that 3∈ {∆(G) + 1−p, m(G)−p}if and only if ∆(G) =p+ 2 orm(G) =p+ 3.
IProposition 5 (♣). For every fixed integerp≥2, the problem of deciding whether a graph Ghas a b-coloring with 3 colors isNP-complete when∆(G) =p+ 2 orm(G) =p+ 3.
Since b-Chromatic Number and b-Coloring are known to be NP-complete when k= ∆(G) + 1 [15], we make the following observation which is of relevance to us since in Section 5.2, we show thatb-ColoringisFPTparameterized by ∆(G) +`k(G).
IObservation 6. b-Chromatic Numberandb-ColoringareNP-complete on graphs with
`k(G) = 0, where kis the integer associated with the respective problem.
4 Dichotomy Algorithms
In this section we give the algorithms in our dichotomy result, proving Theorem 1(iii). We show that for fixedk∈N, the problem of deciding whether a graphGadmits ab-coloring with kcolors is polynomial-time solvable when k=m(G) (Sect. 4.2), whenk= ∆(G) (Sect. 4.3), and whenk=m(G)−1 (Sect. 4.4), by providingXP-algorithms for each case.
A natural way of solving the b-Coloringproblem is to first try to identify a set ofk b-vertices, color them bijectively with colors from [k], and for each vertex in the set a set of k−1 neighbors that can be colored in such a way that the vertex becomes a b-vertex for its color. Then try to extend the resulting coloring to the remainder of the graph. We enumerate all such sets and colorings, and show that the extension problem is solvable in polynomial time in each of the above cases.
The strategy of identifying the set of b-vertices and subsets of their neighbors that make themb-vertices was (for instance) also used to give polynomial-time algorithms to compute the b-chromatic number of trees [12] and graphs with large girth [4]. We capture it by defining the notion of ab-precoloringin the next subsection.
4.1 b-Precolorings
All algorithms in this section are based on guessing a proper coloring of several vertices in the graph, for which we now introduce the necessary terminology and establish some preliminary results.
IDefinition 7(Precoloring). Let Gbe a graph and k∈N. A precoloringwithk colors of a graphG is an assignment of colors to a subset of its vertices, i.e. forX ⊆V(G), it is a map γX:X →[k]. We callγX proper, if it is a proper coloring ofG[X]. We say that a coloring γ:V(G)→[k] extendsγX, if γ|X=γX.
We use the following notation. For two precolorings γX andγY withX∩Y =∅, we denote byγX∪γY the precoloring that colors the vertices in X according toγX and the vertices inY according toY, i.e. the precoloringγX∪Y ..=γX∪γY defined as follows: for all v∈X∪Y, ifv∈X, thenγX∪Y(v) =γX, and ifv∈Y thenγX∪Y(v) =γY(v).
Next, we define a special type of precoloring with the property that any proper coloring that extends it is ab-coloring of the graph.
IDefinition 8 (b-Precoloring). Let Gbe a graph,k∈N,X ⊆V(G)and γX a precoloring.
We callγX a b-precoloring withkcolorsifγX is ab-coloring ofG[X]. Ab-precoloring γX is called minimal if for anyY ⊂X,γX|Y is not ab-precoloring.
It is immediate that anyb-coloring can be obtained by extending a minimalb-precoloring, a fact that we capture in the following observation.
IObservation 9. Let G be a graph,k∈N, andγ ab-coloring ofG withk colors. Then, there is a set X ⊆V(G)such that γ|X is a minimal b-precoloring.
The next observation captures the structure of minimal b-precolorings with k colors.
Roughly speaking, each such precoloring only colors a set ofk b-vertices and for eachb-vertex a set ofk−1 of its neighbors that make that vertex theb-vertex of its color. We will use this property in the enumeration algorithm in this section to guarantee that we indeed enumerate all minimalb-precolorings with a given number of colors.
IObservation 10. Let γX be a minimal b-precoloring with k colors. Then, X =B∪Z, where
(i) B ={x1, . . . , xk} and fori∈[k],γX(xi) =i, and (ii) Z =S
i∈[k]Zi, whereZi∈ Nk−1(xi)
andγX(Zi) = [k]\ {i}.
We are now ready to give the enumeration algorithm for minimalb-precolorings.
ILemma 11 (♣). Let G be a graph on n vertices and k ∈ N. The number of minimal b-precolorings withk colors ofGis at most
β(k)..=nk·∆k(k−1)·(k−1)!k, (1)
where∆..= ∆(G)and they can be enumerated in timeβ(k)·kO(1).
4.2 Algorithm for k = m(G)
Our first application of Lemma 11 is to solve theb-Coloringproblem in the case when k=m(G) in timeXPparameterized byk. It turns out that in this case, we are dealing with aYes-instance as soon as we found ab-precoloring in the input graph that also colors all high-degree vertices (see Claim 12.1).
ITheorem 12. Let G be a graph. There is an algorithm that decides whether G has a b-coloring with k=m(G) colors in timenk2·2O(k2logk).
Proof. LetD⊆V(G) denote the set of vertices inGthat have degree at least k. Note that by the definition ofm(G), we have that|D| ≤k.
IClaim 12.1(♣). Ghas ab-coloring withk colors if and only ifGhas ab-precoloringγX
such that D⊆X and there exists S⊆D such thatγX|(X\S) is a minimalb-precoloring.
The algorithm enumerates all minimalb-precolorings withkcolors and for each such precol- oring, it enumerates all colorings of the verticesD. If combining one such pair of precolorings gives ab-precoloring, it returns a greedy extension of it; otherwise it reports that there is no b-coloring withkcolors, see Algorithm 1.
Algorithm 1Algorithm forb-Coloringwithk=m(G).
Input :A graphG
Output :Ab-coloring withm(G) colors if it exists,Nootherwise.
1 foreachminimal b-precoloringγX:X →[k]do
2 foreachprecoloringγD\X: (D\X)→[k]do
3 if γX∪D..=γX∪γD\X is proper then returna greedy extension of γX∪D;
4 returnNo;
The correctness of the algorithm follows from the fact that it enumerates all precolorings that can satisfy Claim 12.1. We discuss its runtime. By Lemma 11, we can enumerate all minimalb-precolorings withkcolors in timeβ(k)·kO(1). For each such minimalb-precoloring, we also enumerate all colorings ofD. Since|D| ≤k, this gives an additional factor ofkk to the runtime which (with ∆≤n) then amounts toβ(k)·kk·kO(1)≤nk2·2O(k2logk). J
4.3 Algorithm for k = ∆(G)
Next, we turn to the case when k = ∆(G). Here the strategy is to again enumerate all minimal b-precolorings, and then for each such precoloring we check whether it can be extended to the remainder of the graph. Formally, we use an algorithm for the following problem as a subroutine.
Input: A graphG, an integerk, and a precoloringγX:X→[k] of a setX ⊆V(G) Question: DoesGhave a proper coloring withkcolors extendingγX?
Precoloring Extension (PrExt)
Naturally, Precoloring Extensionis a hard problem, since it includesGraph Col- oringas the special case whenX =∅. However, when ∆(G)≤k−1, then the problem is trivially solvable: we simply check if the precoloring at the input is proper and if so, we compute an extension of it greedily. Since each vertex has degree at mostk−1, there is always at least one color available. The case whenk = ∆(G) has also been shown to be solvable in polynomial time.
ITheorem 13 (Thm. 3 in [5], see also [7]). There is an algorithm that solves Precoloring Extensionin polynomial time whenever ∆(G)≤k.
ITheorem 14. There is an algorithm that decides whether a graphGhas ab-coloring with
∆(G)colors in timenk+O(1)·2O(k2logk).
Proof (sketch). For each minimal b-precoloringγX, we apply the algorithm forPrExtof Theorem 13. If it finds a proper coloring extendingγX, we return it, and if there is no successful run of the algorithm forPrExt, we returnNo. The details are given in the full
version [13]. J
4.4 Algorithm for k = m(G) − 1
Before we proceed to describe the algorithm for b-Coloring when k = m(G)−1, we show that the algorithm of Theorem 13 can be used for a slightly more general case of Precoloring Extension, namely the case when all high-degree vertices in the input instance are precolored.
ILemma 15(♣). There is an algorithm that solves an instance(G, k, γX)of Precoloring Extensionin polynomial time whenevermaxv∈V(G)\Xdeg(v)≤k.
ITheorem 16. There is an algorithm that decides whether a graphGhas a b-coloring with k=m(G)−1colors in time nk2+O(1)·2k2logk.
Proof (sketch). Let D denote the set of vertices of degree at leastk+ 1 in G. By the definition ofm(G), we have that|D| ≤k+ 1. We first enumerate all minimalb-precolorings of G, and for each such precoloring, we enumerate all precolorings of D. Since given a b-precoloringγX withD⊆X, we have that every vertex in V(G)\X has degree at mostk, we can apply the algorithm of Lemma 15 to verify whether there is a proper coloring ofG that extendsγX. If so, we output that extension. If no such precoloring can be found, then we conclude that we are dealing with aNo-instance. We give the details of the algorithm and its correctness proof in the full version [13].
It remains to argue the runtime. We enumerateβ(k) (see (1)) minimalb-precolorings in timeβ(k)·kO(1) using Lemma 11. For each such precoloring, we enumerate all precolorings of D\X. Since|D| ≤k+ 1, there are at most kk+1 such colorings. Finally, we run the algorithm forPrExt due to Lemma 15 which takes timenO(1). The total runtime becomes
β(k)·kO(1)·kk+1·nO(1)≤nk2+O(1)·2k2logk. J
5 Maximum Degree Parameterizations
In this section we consider parameterizations ofb-Coloring that involve the maximum degree ∆(G) of the input graphG. In Section 5.1 we show that we can solveb-Coloring when k = m(G) in time FPT parameterized by ∆(G) and in Section 5.2 we show that b-ColoringisFPTparameterized by ∆(G) +`k(G).
Both algorithms presented in this section make use of the following reduction rule, which has already been applied in [16, 17] to obtain theFPTalgorithm for the problem of deciding whether a graphGhas ab-coloring withk= ∆(G) + 1 colors, parameterized byk.
IReduction Rule 17 ([16, 17]). Let (G, k) be an instance of b-Coloring. If there is a vertexv∈V(G)such that every vertex in N[v] has degree at mostk−2, then reduce(G, k) to(G−v, k).
5.1 FPT Algorithm for k = m(G) parameterized by ∆(G)
Sampaio [17] and Panolan et al. [16] independently showed that parameterized by ∆(G), it can be decided inFPT time whether a graph Ghas a b-coloring with ∆(G) + 1 colors.
In this section we show that in the same parameterization, it can be decided inFPTtime whether a graph has ab-coloring withm(G) colors.
ITheorem (Thm. 2, restated). There is an algorithm that given a graphG on nvertices decides whether G has a b-coloring with k = m(G) colors in time 2O(k4·∆) +nO(1) <
2O(∆5)+nO(1), where∆..= ∆(G).
Proof. We apply Reduction Rule 17 exhaustively toGand consider the following 3-partition (D, T, R) ofV(G), whereDcontains the vertices of degree at leastk,T the vertices of degree precisely k−1 andR the remaining vertices, i.e. R..=V(G)\(D∪T). Since we applied Reduction Rule 17 exhaustively, we make
IObservation 2.1. Every vertex inR has at least one neighbor inD∪T.
We pick an inclusion-wise maximal setB⊆D∪T such that for each pair of distinct vertices b1, b2∈B, we have thatdist(b1, b2)≥4.
Case 1 (|B∩T|< k).1 We show that for any vertex inu∈V(G)\B, there is a vertex v ∈B such thatdist(u, v)≤4. Supposeu∈D∪T. Since we did not include uinB, it immediately follows that there is somev∈B such thatdist(u, v)<4. Now supposeu∈R.
By Observation 2.1, u has a neighbor w in D∪T and by the previous argument, there is a vertex v ∈B such that dist(w, v) <4. We conclude that dist(u, v) ≤4. Using this observation, we now show that in this case, the number of vertices inGis polynomial ink and ∆.
IClaim 2.2. If |B∩T|< k, then|V(G)| ≤ O(k4·∆).
Proof. Note that (B∪D, S1, . . . , S4) constitutes a partition ofV(G), whereSi is the set of vertices ofV(G)\(B∪D) that are at distance exactlyifromB. Since|B∩T|< kand|D| ≤k, we have that|B∪D|<2k, and therefore|S1|<2k·∆. By the definition ofm(G), all the vertices inS1∪. . .∪S4have degree at mostk−1. This implies that|Si|<(k−1)i−1·2k·∆.
We conclude that the number of vertices inGis at most 2k+2k·∆·P4
i=1(k−1)i−1=O(k4·∆).
C By Claim 2.2, we can solve the instance in Case 1 in time 2O(k4·∆) using the algorithm of Panolan et al. [16].
Case 2 (|B ∩ T| ≥ k). Let B0 ⊆ B∩T with |B0| = k and denote this set by B0 = {x1, x2, . . . , xk}. We show that we can construct ab-coloring γ:V(G)→[k] ofGsuch that for i∈[k], xi is theb-vertex of colori. For i∈[k], we letγ(xi)..=i. Next, we color the vertices inD. Recall that|D| ≤k, so we can color the vertices inD injectively with colors from [k], ensuring that this will not create a conflict on any edge in G[D]. Furthermore, consider i, j∈[k] withi6=j. Sincedist(xi, xj)≥4, we have thatN(xi)∩N(xj) =∅. In particular, there is no vertex inD that has two or more neighbors inB0. To summarize, we can conclude that we can letγ color the vertices ofD in such a way that:
(i) γ is injective onD, and
(ii) γ is a proper coloring ofG[B0∪D].
These two items imply that for eachxi (i∈[k]), its neighborsN(xi)∩D receive distinct colors which are also different fromi. Let`..=|N(xi)∩D|. It follows that we can letγ color the remaning (k−1)−`neighbors ofxi in an arbitrary bijective manner with the (k−1)−` colors that do not yet appear in the neighborhood ofxi.
After this process, xi is a b-vertex for color i. We proceed in this way for all i ∈[k].
Since fori, j∈[k] with i6=j we have thatdist(xi, xj)≥4, it follows that there are no edges between N[xi] andN[xj] in G. Hence, we did not introduce any coloring conflict in the previous step. Now, all vertices inGthat have not yet received a color byγ have degree at mostk−1, so we can extendγ to a proper coloring ofGin a greedy fashion.
We summarize the whole procedure in Algorithm 2. We now analyze its runtime. Clearly,
1 This case is almost identical to [16, Case II in the proof of Theorem 2].
Algorithm 2An algorithm that either constructs ab-coloring of a graphGwithm(G) colors, or reports that there is none, and runs inFPTtime parameterized by ∆(G).
Input :A graphGwithk=m(G)// More generally, graph G with
`k(G)≤k
Output :Ab-coloring withkcolors ofGif it exists, andNootherwise.
1 Apply Reduction Rule 17 exhaustively;
2 Let (D, T, R) be a partition ofV(G) such that for allx∈D, degG(x)≥k, for all x∈T, degG(x) =k−1, andR=V(G)\(D∪T);
3 LetB⊆D∪T be a maximal set such that for distinctb1, b2∈B,dist(b1, b2)≥4;
4 if |B∩T|< kthen// Case 1
5 Solve the instance in time 2O(k4·∆) using theb-Coloringalgorithm [16];
6 if the algorithm of [16] returned ab-coloring γthen returnγ;
7 else returnNo;
8 else// Case 2, i.e. |B∩T| ≥k
9 Pick a size-ksubset ofB∩T, sayB0..={x1, . . . , xk};
10 Initialize ak-coloringγ:V(G)→[k];
11 Fori∈[k], letγ(xi)..=i;
12 Letγ color the vertices ofD injectively such thatγremains proper onG[B0∪D];
13 Fori∈[k], letγcolorN(xi)∩D such thatxi is theb-vertex of colori;
14 Extend the coloringγ greedily to the remainder ofG;
15 returnγ;
exhaustively applying Reduction Rule 17 can be done in timenO(1). As mentioned above, Case 1 can be solved in time 2O(k4·∆). In Case 2, the coloring ofG[B0∪D] can be found in timeO(k2), and extending the coloring to the remainder ofGcan be done in time nO(1).
The claimed bound follows. J
IRemark 18 (♣). Algorithm 2 solves the problem of deciding whetherGadmits ab-coloring withkcolors in time 2O(k4·∆)+nO(1) whenever`k(G)≤k.
Furthermore, in the proof of Theorem 2, we provide a polynomial kernel for the problem: In Case 1, we have a kernelized instance onO(k4·∆) vertices (see Claim 2.2) and in Case 2, we always have aYes-instance.
ICorollary 19. The problem of deciding whether a graph Ghas ab-coloring withk=m(G) colors admits a kernel on O(k4·∆) =O(∆5)vertices.
5.2 FPT Algorithm Parameterized by ∆(G) + `
k(G)
The next parameterization ofb-Coloringinvolving the maximum degree that we consider is by ∆(G) +`k(G). We show that in this case, the problem is FPT. By Observation 6 we know thatb-ColoringisNP-complete on graphs with`k(G) = 0, and by Theorem 1, it is NP-complete even whenk= 3 and ∆(G) = 4. Hence, there is noFPT- norXP-algorithm for a parameterization using only one of the two above mentioned parameters unlessP=NP. Note that the algorithm we provide in this section can be used to solve the case ofk=m(G) for which we gave a separate algorithm in Section 5.1, see Algorithm 2. However, Algorithm 2 is much simpler than the algorithm presented in this section, and simply applying the following algorithm for the casek=m(G) results in a runtime of 2O(kk+3·∆)+nO(1)which is far worse than the runtime of 2O(k4·∆)+nO(1) of Theorem 2.
ITheorem(Thm. 3, restated). There is an algorithm that given a graph Gon n vertices decides whetherGhas ab-coloring withkcolors in time 2O(`·∆·min{`,∆}`+2)+nO(1), where
∆..= ∆(G)and`..=`k(G).
Proof. The overall strategy of the algorithm is similar to Algorithm 2. We can make the following assumptions. First, if`≤k, then we can apply Algorithm 2 directly to solve the instance at hand, see Remark 18. Hence we can assume thatk < `. Furthermore,k≤∆ + 1, otherwise we are dealing with a trivialNo-instance; we have that k≤min{`−1,∆ + 1}.
Furthermore, we can assume thatk >2, otherwise the problem is trivially solvable in time polynomial inn.
We consider a partition (D, T, R) ofV(G), where the vertices inD have degree at least k, the vertices inT have degreek−1 and the vertices inR have degree less thank−1. We assume that Reduction Rule 17 has been applied exhaustively, so Observation 2.1 holds, i.e.
every vertex inR has at least one neighbor inD∪T.
Now, we pick an inclusion-wise maximal setB⊆D∪T such that for each pair of distinct verticesb1, b2∈B,distG(b1, b2)≥`+ 3.
Case 1 (|B∩T|< k). By the same argument given in Case 1 of the proof of Theorem 2, we have that any vertex inT∪R is at distance at most`+ 3 from a vertex inB. We now give a bound on the number of vertices inGin terms of `and ∆.
IClaim 3.1 (♣). If |B∩T|< k, then|V(G)|=O(`·∆·min{`,∆}`+2).
By the previous claim, we can solve the instance in time 2O(`·∆·min{`,∆}`+2) in this case, using the exact exponential time algorithm forb-Coloringdue to Panolan et al. [16].
Case 2 (|B∩T| ≥k). LetB0 ⊆B∩T be of size kand denote it by B0 ..={x1, . . . , xk}.
The strategy in this case is as follows: We compute a proper coloring ofG[D], and then modify it so that can be extended to ab-coloring ofG. In this process we will be able to guarantee for eachi∈[k], that eitherxican be theb-vertex for colori, or we will have found another vertex inDthat can serve as the b-vertex of colori. The difficulty here arises from the following situation: Suppose that in the coloring we computed forG[D], a vertexxi has two neighbors inD that received the same color. Then,xi cannot be theb-vertex of colori in any extension of that coloring, since deg(xi) =k−1, andk−1 colors need to appear the neighborhood ofxi for it to be a b-vertex. However, recoloring a vertex inN(xi)∩Dmight create a conflict in the coloring ofG[D]. These potential conflicts can only appear in the connected component ofG[D∪B0] that containsxi. We now show that each component of G[D∪B0] can contain at most one such vertex, by our choice of the setB.
IClaim 3.2 (♣). LetC be a connected component ofG[D∪B0]. Then,C contains at most one vertex from B0.
Throughout the following, fori∈[k], we denote byCi the connected component ofG[D∪B0] that contains xi, and by`i the number of vertices ofCi, i.e.`i ..=|V(Ci)|. By Claim 3.2, Ci6=Cj, for alli, j∈[k], i6=j. We now show that each neighbor ofxi has no neighbor in D∩N[B0] outside ofV(Ci)∪N[xi].
IClaim 3.3(♣). Leti∈[k], andy∈N(xi)\D. Then,NG[y]∩(D∪N[B0])⊆V(Ci)∪N[xi].
LetC∅be the set of connected components ofG[D∪B0] that do not contain any vertex from B0. We observe that any proper coloring ofG[D∪B0] can be obtained from independently coloring the vertices inC1, . . . , Ck, andC∅. If for some i∈[k], Ci is a trivial2 component,
2
C1 C2 C4 C∅ D
T
R
x1 x2 x3 x4
C3
Figure 1 Illustration of the structure of a graph Gin the proof of Theorem 3 where k = 4.
Here,B0 ={x1, . . . , x4} andC1, . . . , C4 are the components ofG[D∪B0] containing x1, . . . , x4, respectively. Note that all vertices inT are of degree 3, all vertices inR of degree at most 2 and all vertices inR have a neighbor inD∪T.
thenN(xi)∩D=∅. Hence, we can assignxi any color without creating any conflict with the remaining vertices inG[D∪B0]. On top of that, Claim 3.3 ensures that assigning a color to a neighbor of anyxi (that is not contained inD) cannot create a coloring conflict with any vertex inD∪N[B0] that is not contained inV(Ci)∪N[xi]. We illustrate the structure ofGin Figure 1.
IClaim 3.4 (♣). Leti∈[k] and letγ:V(Ci)→[k]be a proper coloring of Ci. Then, one can find in time O(k2·`2i)a setYi⊆NG(xi)\D and a proper coloring δ: V(Ci)∪Yi→[k]
of G[V(Ci)∪Yi]that has ab-vertex for colori.
We now wrap up the treatment of this case. We compute a proper k-coloring γ of G[D∪B0] using standard methods [3]. We derive from γ another k-coloring δ of some induced subgraph ofG[D∪NG[B0]] containingD∪B0. For eachi∈[k], we do the following.
With input γ|V(Ci) we compute a proper k-coloringδi of G[V(Ci)∪Yi] using Claim 3.4, where Yi is the set returned by its algorithm, and we let δ|V(Ci)∪Yi ..=δi. Finally, we let δ|V(C∅)..=γ|V(C∅). As fori6=j,Ci andCj are distinct connected components ofG[D∪B0] and by Claim 3.3, this construction is well-defined and there is no color conflict between any pair of verticeszi, zj where zi ∈V(Ci)∪Yi andzj ∈V(Cj)∪Yj for i6=j. Since for eachi∈[k] we applied Claim 3.4,δis ab-precoloring ofG. All vertices inGthat have not received a color so far (recall thatδcolors all vertices inD) have degree at mostk−1, so we can extend the coloringδgreedily to the remainder of Gand eventually obtain ab-coloring ofG. The runtime of 2O(`·∆·min{`,∆}`+2)+nO(1) is argued for in the full version [13]. J Similar to above, we obtained a kernel for the problem. While this result does not provide a polynomial kernel for the parameterization ∆ +`, it does give a polynomial kernel if we consider the problem forfixed values of` and parameter ∆.
ICorollary 20. The problem of deciding whether a graphGadmits ab-coloring withkcolors admits a kernel on O(`·∆·min{`,∆}`+2)vertices, where ∆..= ∆(G)and`..=`k(G).
6 Conclusion
We have presented a complexity dichotomy forb-Coloringwith respect to two upper bounds on theb-chromatic number, in the following sense: We have shown that given a graphGand for fixedk∈ {∆(G) + 1−p, m(G)−p}, it can be decided in polynomial time whetherG has ab-coloring withk colors wheneverp∈ {0,1}and the problem remainsNP-complete wheneverp≥2, already fork= 3.
The most immediate question left open in this work is the parameterized complexity of theb-Coloringproblem whenk∈ {m(G),∆(G), m(G)−1}. In all of these cases, we have providedXP-algorithms, and it would be interesting to see whether these problems are FPT orW[1]-hard. We showed thatb-ColoringisFPTparameterized by ∆(G) +`k(G), where
`k(G) denotes the number of vertices of degree at leastk inG, and this is optimal in the sense that there is noFPTnorXPalgorithm for the problem parameterized by only one of the two invariants. It would be interesting to see if one could devise anFPT-algorithm for the parameterization that replaces the maximum degree by the number of colors.
References
1 Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, and Nicolas Trotignon. Coloring Graphs with Constraints on Connectivity. J. Graph Theory, 85(4):814–838, 2017.
2 Dominique Barth, Johanne Cohen, and Taoufik Faik. On theb-continuity property of graphs.
Discrete Appl. Math., 155:1761–1768, 2007.
3 Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set Partitioning via Inclusion- Exclusion. SIAM J. Comput., 39(2):546–563, 2009.
4 Victor Campos, Carlos Vinicius G. C. Lima, and Ana Silva. Graphs of girth at least 7 have high b-chromatic number. Eur. J. Combin., 48:154–164, 2015.
5 Miroslav Chelbík and Janka Chlebíkova. Hard Coloring Problems in Low Degree Planar Bipartite Graphs. Discrete Appl. Math., 154:1960–1965, 2006.
6 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 1st edition, 2015.
7 Konrad K. Dabrowski, François Dross, Matthew Johnson, and Daniël Paulusma. Filling the complexity gaps for colouring planar and bounded degree graphs. InProc. IWOCA ’15, volume 9538 ofLecture Notes in Computer Science, pages 100–111. Springer, 2015.
8 Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity.
Texts in Computer Science. Springer, 2013.
9 Esther Galby, Paloma T. Lima, Daniël Paulusma, and Bernard Ries. On the Parameterized Complexity ofk-Edge Colouring, 2019. arXiv:1901.01861.
10 Frédéric Havet, Cláudia Linhares Sales, and Leonardo Sampaio. b-Coloring of Tight Graphs.
Discrete Appl. Math., 160:2709–2715, 2012.
11 Frédéric Havet and Leonardo Sampaio. On the Grundy and b-chromatic numbers of a graph.
Algorithmica, 65(4):885–899, 2013.
12 Robert W. Irving and David F. Manlove. Theb-Chromatic Number of a Graph. Discrete Appl. Math., 91(1-3):127–141, 1999.
13 Lars Jaffke and Paloma T. Lima. A Complexity Dichotomy for Critical Values of the b- Chromatic Number of Graphs. CoRR, 2018. arXiv:1811.03966.
14 Richard M. Karp. Reducibility among combinatorial problems. InComplexity of Computer Computations, pages 85–103. Springer, 1972.
15 Jan Kratochvíl, Zsolt Tuza, and Margit Voigt. On theb-Chromatic Number of Graphs. In Proc. WG ’02, volume 2573 ofLNCS, pages 310–320, 2002.
16 Fahad Panolan, Geevarghese Philip, and Saket Saurabh. On the parameterized complexity of b-Chromatic Number. J. Comput. Syst. Sci., 84:120–131, 2017.
17 Leonardo Sampaio. Algorithmic Aspects of Graph Coloring Heuristics. PhD thesis, Université Nice Sophia Antipolis, France, 2012.
