On directed local chromatic number, shift graphs, and Borsuk-like graphs

DOI10.1002/JGT.20494MaRDI QIDQ3067063zbMATH OpenOpenAlexFDO

Authors Gábor Simonyi, Gábor Tardos

Publication date 20 January 2011

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.2897

zbMATH Keywords

topological methodshift graphlocal chromatic numberSchrijver graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Abstract: 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 the upper integer part of t/4+1.

Recommendations

• Relations between the local chromatic number and its directed version
• scientific article; zbMATH DE number 5763218
• On generalized shift graphs
• Local chromatic number and distinguishing the strength of topological obstructions
• Local chromatic number and Sperner capacity

Cites work

• scientific article; zbMATH DE number 3845607 (Why is no real title available?)
• scientific article; zbMATH DE number 5704224 (Why is no real title available?)
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• An extremal problem for two families of sets
• Evenly distributed subsets of \(S^ n\) and a combinatorial application
• Fractional chromatic numbers of cones over graphs
• Inequalities for two set systems with prescribed intersections
• Kneser's conjecture, chromatic number, and homotopy
• Local chromatic number and distinguishing the strength of topological obstructions
• Local chromatic number, Ky Fan's theorem, and circular colorings
• On products of idempotent matrices
• Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities
• Sur le coloriage des graphs

Cited in

(6)

• Dynamic coloring of graphs having no \(K_5\) minor
• The fractional version of Hedetniemi's conjecture is true
• Contact graphs of boxes with unidirectional contacts
• Relations between the local chromatic number and its directed version
• Resource-sharing system scheduling and circular chromatic number
• Coloring chains for compression with uncertain priors

This page was built for publication: On directed local chromatic number, shift graphs, and Borsuk-like graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3067063)