Premium
Chromatic neighborhood sets
Author(s) -
Molloy Michael
Publication year - 1999
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/(sici)1097-0118(199908)31:4<303::aid-jgt5>3.0.co;2-g
Subject(s) - combinatorics , mathematics , conjecture , chromatic scale , vertex (graph theory) , graph , discrete mathematics , critical graph , graph power , line graph
For each vertex v in a graph G , we denote by χ v the chromatic number of the subgraph induced by its neighborhood, and we set χ N ( G ) = {χ v : v ∈ V ( G )}. We characterize those sets X for which there exists some G of prescribed size with X = χ N ( G ), and prove a related conjecture of Fajtlowicz. We also discuss those graphs that are extremal with respect to χ N (G). © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 303–311, 1999