2018arXiv (Cornell University)Open access

Choosability in bounded sequential list coloring

Simone Gama, Rosiane de Freitas, Mário Salvatierra

Open full text 0 citations

Abstract

The list coloring problem is a variation of the classical vertex coloring problem, extensively studied in recent years, where each vertex has a restricted list of allowed colors, and having some variations as the $(γ,μ)$-coloring, where the color lists have sequential values with known lower and upper bounds. This work discusses the choosability property, that consists in determining the least number $k$ for which it has a proper list coloring no matter how one assigns a list of $k$ colors to each vertex. This is a $Π_2^P$-complete problem, however, we show that $k$-$(γ,μ)$-choosability is an $NP$-problem due to its relation with the $k$-coloring of a graph and application of methods of proof in choosability for some classes of graphs, such as complete bipartite graph, which is $ 3 $-choosable, but $ 2 $-$(γ,μ)$-choosable.

Open-access reader

About this research paper

What this paper is about

The list coloring problem is a variation of the classical vertex coloring problem, extensively studied in recent years, where each vertex has a restricted list of allowed colors, and having some variations as the $(γ,μ)$-coloring, where the color lists have sequential values with known lower and upper bounds. This work discusses the choosability property, that consists in determining the least number $k$ for which it has a proper list coloring no matter how one assigns a list of $k$ colors to each vertex. This is a $Π_2^P$-complete problem, however, we show that $k$-$(γ,μ)$-choosability is an $NP$-problem due to its relation with the $k$-coloring of a graph and application of methods of proof in choosability for some classes of graphs, such as complete bipartite graph, which is $ 3 $-choosable, but $ 2 $-$(γ,μ)$-choosable.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

The list coloring problem is a variation of the classical vertex coloring problem, extensively studied in recent years, where each vertex has a restricted list of allowed colors, and having some variations as the $(γ,μ)$-coloring, where the color lists have sequential values with known lower and upper bounds. This work discusses the choosability property, that consists in determining the least number $k$ for which it has a proper list coloring no matter how one assigns a list of $k$ colors to each vertex. This is a $Π_2^P$-complete problem, however, we show that $k$-$(γ,μ)$-choosability is an $NP$-problem due to its relation with the $k$-coloring of a graph and application of methods of proof in choosability for some classes of graphs, such as complete bipartite graph, which is $ 3 $-choosable, but $ 2 $-$(γ,μ)$-choosable.

Key concepts: List coloring, Fractional coloring, Complete coloring, Combinatorics, Bipartite graph, Greedy coloring, Graph coloring, Vertex (graph theory)

Related papers

Back to paper searchBrowse research topicsOriginal source
Choosability in bounded sequential list coloring — Research Paper | ScholarLens