Proper interval vertex colorings of graphs

• Published in: Applied mathematics and computation 2024-09, Vol.477, p.128813, Article 128813
• Main Authors: Madaras, Tomáš, Matisová, Daniela, Onderko, Alfréd, Šárošiová, Zuzana
• Format: Article
• Language: English
• Subjects: Greedy coloring; Interval vertex coloring; Proper coloring
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2024.128813

In this paper, we explore proper vertex colorings of graphs with the additional constraint that the colors used on the closed neighborhood of every vertex form an integer interval; such colorings are called proper closed interval vertex colorings (PCIV colorings for short). As not every graph admits such a coloring, we are concerned with the problem of deciding which graphs admit PCIV colorings, describing several sufficient conditions (among them unique and 3-colorability, partial decomposability into two bipartite graphs, and density constraints) as well as some constructions of PCIV uncolorable graphs. We also present an algorithmic support for PCIV colorability based on a modification of the standard greedy algorithm for standard proper coloring. •Propose a new proper coloring (PCIV coloring) where colors on closed neighborhoods of vertices form integer intervals.•Particular sufficient conditions for PCIV colorability are proved.•Several constructions of PCIV uncolorable graphs are presented.•Greedy algorithm for finding a PCIV coloring is developed.