Facial packing vertex-coloring of subdivided plane graphs

A facial packing vertex-coloring of a plane graph G is a coloring of its vertices with colors 1,…,k such that every facial path containing two vertices with the same color i has at least i+2 vertices. The smallest positive integer k such that G admits a facial packing vertex-coloring with colors 1,…...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2019-03, Vol.257, p.95-100
Main Authors: Czap, Július, Jendrol’, Stanislav, Šugerek, Peter, Valiska, Juraj
Format: Article
Language:English
Subjects:
Apexes
Graph coloring
Graph theory
Plane graph
Subdivision
Vertex-coloring
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A facial packing vertex-coloring of a plane graph G is a coloring of its vertices with colors 1,…,k such that every facial path containing two vertices with the same color i has at least i+2 vertices. The smallest positive integer k such that G admits a facial packing vertex-coloring with colors 1,…,k is denoted by pf(G). Let Si(G) denote the graph obtained from G by subdividing each of its edges precisely i times, i≥0. In this paper we deal with a question whether pf(Si(G)) is bounded.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2018.10.022