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

DOI10.1002/JGT.20494zbMATH Open1222.05076arXiv0906.2897OpenAlexW2069566112MaRDI QIDQ3067063FDOQ3067063

Authors: Gábor Simonyi, Gábor Tardos 

Publication date: 20 January 2011

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

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.

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

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

zbMATH Keywords

topological methodshift graphlocal chromatic numberSchrijver graph

Mathematics Subject Classification ID

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

Cites Work

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

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)