Path chromatic numbers of graphs | Zendy

Akiyama Jin | Zendy; Era Hiroshi | Zendy; Gervacio Severino V. | Zendy; Watanabe Mamoru | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research