Premium
On directed local chromatic number, shift graphs, and Borsuk‐like graphs
Author(s) -
Simonyi Gábor,
Tardos Gábor
Publication year - 2011
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.20494
Subject(s) - chromatic scale , combinatorics , mathematics , graph , critical graph , discrete mathematics , foster graph , friendship graph , line graph , graph power
We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of “topologically t ‐chromatic” graphs. We show that this minimum for large enough t ‐chromatic Schrijver graphs and t ‐chromatic generalized Mycielski graphs of appropriate parameters is ⌈ t /4⌉+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 65‐82, 2010