Loading Events

« All Events


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

May 24 Friday @ 4:30 PM - 5:30 PM

Room B232, IBS (기초과학연구원)


A $b$-coloring of a graph $G$ is 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. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors.
The $b$-chromatic number of a graph $G$, denoted by $\chi_b(G)$, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the $b$-Coloring problem, whenever the value of $k$ is close to one of two upper bounds on $\chi_b(G)$: The maximum degree $\Delta(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 of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k \in\{\Delta(G) + 1 − p, m(G) − p\}$, the problem is polynomial-time solvable whenever $p\in\{0, 1\}$ and, even when $k = 3$, it is NP-complete whenever $p \ge 2$.
We furthermore consider parameterizations of the $b$-Coloring problem that involve the maximum degree $\Delta(G)$ of the input graph $G$ and give two FPT-algorithms. First, we show that deciding whether a graph G has a $b$-coloring with $m(G)$ colors is FPT parameterized by $\Delta(G)$. Second, we show that $b$-Coloring is FPT parameterized by $\Delta(G) + \ell_k(G)$, where $\ell_k(G)$ denotes the number of vertices of degree at least $k$.
This is joint work with Paloma T. Lima.


May 24 Friday
4:30 PM - 5:30 PM
Event Category:
Event Tags:


Room B232
IBS (기초과학연구원)


Sang-il Oum
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
Discrete Mathematics Group (DIMAG)
Pioneer Research Center for Mathematical and Computational Sciences
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr
Copyright (c) IBS 2018. All rights reserved.