Proper interval vertex colorings of graphs

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...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2024.128813