Israel R. Curbelo ; Hannah R. Malko - On the on-line coloring of unit interval graphs with proper interval representation

dmtcs:14088 - Discrete Mathematics & Theoretical Computer Science, February 21, 2025, vol. 27:2 - https://doi.org/10.46298/dmtcs.14088
On the on-line coloring of unit interval graphs with proper interval representationArticle

Authors: Israel R. Curbelo ; Hannah R. Malko

    We define the problem as a two-player game between Algorithm and Builder. The game is played in rounds. Each round, Builder presents an interval that is neither contained in nor contains any previously presented interval. Algorithm immediately and irrevocably assigns the interval a color that has not been assigned to any interval intersecting it. The set of intervals form an interval representation for a unit interval graph and the colors form a proper coloring of that graph. For every positive integer ω, we define the value R(ω) as the maximum number of colors for which Builder has a strategy that forces Algorithm to use R(ω) colors with the restriction that the unit interval graph constructed cannot contain a clique of size ω+1. In 1981, Chrobak and \'{S}lusarek showed that R(ω)2ω1. In 2005, Epstein and Levy showed that R(ω)3ω/2. This problem remained unsolved for ω3. In 2023, Biró and Curbelo showed that R(3)=5. In this paper, we show that R(4)=7


    Volume: vol. 27:2
    Section: Combinatorics
    Published on: February 21, 2025
    Accepted on: February 13, 2025
    Submitted on: August 21, 2024
    Keywords: Mathematics - Combinatorics,Computer Science - Data Structures and Algorithms,05C15 (Primary) 68W27 (Secondary)

    Consultation statistics

    This page has been seen 180 times.
    This article's PDF has been downloaded 65 times.