Seminars in May 2019

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

    IBS/KAIST Joint Discrete Math Seminar

    A complexity dichotomy for critical values of the b-chromatic number of graphs
    Lars Jaffke
    University of Bergen
    2019/05/20 Mon 4:30PM-5:30PM (IBS, B232)
    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 χ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 χ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 of degree at least i−1. We obtain a dichotomy result stating that for fixed k∈{Δ(G)+1−p,m(G)−p}, the problem is polynomial-time solvable whenever p∈{0,1} and, even when k=3, it is NP-complete whenever p≥2.
    We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree Δ(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 Δ(G). Second, we show that b-Coloring is FPT parameterized by Δ(G)+ℓk(G), where ℓk(G) denotes the number of vertices of degree at least k.
    This is joint work with Paloma T. Lima.
    Tags:

  • Xin Zhang, On equitable tree-colorings of graphs

    IBS/KAIST Joint Discrete Math Seminar

    On equitable tree-colorings of graphs
    Xin Zhang (张欣)
    Xidian Univeristy, China
    2019/05/16 4:30PM-5:30PM (IBS, B232)
    An equitable tree-k-coloring of a graph is a vertex coloring using k distinct colors such that every color class (i.e, the set of vertices in a common color) induces a forest and the sizes of any two color classes differ by at most one. The minimum integer k such that a graph G is equitably tree-k-colorable is the equitable vertex arboricity of G, denoted by vaeq(G). A graph that is equitably tree-k-colorable may admits no equitable tree-k′-coloring for some k′>k. For example, the complete bipartite graph K9,9 has an equitable tree-2-coloring but is not equitably tree-3-colorable. In view of this a new chromatic parameter so-called the equitable vertex arborable threshold is introduced. Precisely, it is the minimum integer k such that G has an equitable tree-k′-coloring for any integer k′≥k, and is denoted by va∗eq(G). The concepts of the equitable vertex arboricity and the equitable vertex arborable threshold were introduced by J.-L. Wu, X. Zhang and H. Li in 2013. In 2016, X. Zhang also introduced the list analogue of the equitable tree-k-coloring. There are many interesting conjectures on the equitable (list) tree-colorings, one of which, for example, conjectures that every graph with maximum degree at most Δ is equitably tree-k-colorable for any integer k≥(Δ+1)/2, i.e, va∗eq(G)≤⌈(Δ+1)/2⌉. In this talk, I review the recent progresses on the studies of the equitable tree-colorings from theoretical results to practical algorithms, and also share some interesting problems for further research.

  • Sang June Lee (이상준), On strong Sidon sets of integers

    IBS/KAIST Joint Discrete Math Seminar

    On strong Sidon sets of integers
    Sang June Lee
    Duksung Women’s University, Seoul
    2019/05/08 Wed 4:30PM-5:30PM (IBS, Room B232)
    Let N be the set of natural numbers. A set A⊂N is called a Sidon set if the sums a1+a2, with a1,a2∈S and a1≤a2, are distinct, or equivalently, if
    |(x+w)−(y+z)|≥1
    for every x,y,z,w∈S with x<y≤z<w. We define strong Sidon sets as follows:</p>

    For a constant α with 0≤α<1, a set S⊂N is called an α-strong Sidon set if
    |(x+w)−(y+z)|≥wα
    for every x,y,z,w∈S with x<y≤z<w.

    The motivation of strong Sidon sets is that a strong Sidon set generates many Sidon sets by altering each element a bit. This infers that a dense strong Sidon set will guarantee a dense Sidon set contained in a sparse random subset of N.

    In this talk, we are interested in how dense a strong Sidon set can be. This is joint work with Yoshiharu Kohayakawa, Carlos Gustavo Moreira and Vojtěch Rödl.

    Tags:

Monthly Archives