Premium
Path chromatic numbers of graphs
Author(s) -
Akiyama Jin,
Era Hiroshi,
Gervacio Severino V.,
Watanabe Mamoru
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130506
Subject(s) - combinatorics , mathematics , chromatic scale , vertex (graph theory) , graph , colored , induced path , planar graph , path (computing) , discrete mathematics , longest path problem , chordal graph , computer science , materials science , composite material , programming language
Abstract Let the finite, simple, undirected graph G = ( V ( G ), E ( G )) be vertex‐colored. Denote the distinct colors by 1,2,…, c. Let V i be the set of all vertices colored j and let < V i be the subgraph of G induced by V i . The k ‐path chromatic number of G , denoted by χ( G ; P k ), is the least number c of distinct colors with which V ( G ) can be colored such that each connected component of V i is a path of order at most k , 1 ⩽ i ⩽ c. We obtain upper bounds for χ( G ; P k ) and χ( G ; P ∞ ) for regular, planar, and outerplanar graphs.