Interval vertex coloring

Mária Maceková

doi:10.1016/j.amc.2024.128559

Interval vertex coloring

2024-06-01

1

PRE

AI

DOI：10.1016/j.amc.2024.128559

原文链接

原文求助

摘要

En 中文

In this paper we consider various vertex versions of interval edge colorings. We distinguish two types of interval vertex colorings - an open and a closed interval vertex coloring, which are defined in such a way that colors used on open or closed neighborhood of each vertex form an integer interval, respectively. These colorings need not to be necessarily proper, and as coloring of all vertices with only one color is both open and closed, a natural goal is to maximize the total number of colors used for these colorings. We discuss some properties of the corresponding chromatic numbers and conditions for the existence of a proper (open and closed) interval vertex colorings. In the case of open interval coloring we show that only bipartite graphs admit a proper open interval vertex coloring. We also describe a technique for obtaining a closed interval vertex coloring of a tree with the maximum possible number of colors, where the resulting coloring is in fact proper. Finally, we propose some open problems concerning interval vertex colorings in general.

Keyword:

Vertex coloring

Interval chromatic number

Tree

Caterpillar tree

Interval vertex coloring

摘要

期刊

机构

引用论文