Interleaved adjoints of directed graphs

DOI10.1016/J.EJC.2011.03.013MaRDI QIDQ648963zbMATH OpenOpenAlexFDO

Authors Jan Foniok, J. Nešetřil, Claude Tardif

Publication date 29 November 2011

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.1200, https://e-space.mmu.ac.uk/601177/1/0905.1200v2.pdf

zbMATH Keywords

fairnesshomomorphismcircular chromatic numberfractional chromatic numberminimum mean cyclescheduling by edge reversal

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Abstract: For an integer k >= 1, the k-th interlacing adjoint of a digraph G is the digraph i_k(G) with vertex-set V(G)^k, and arcs ((u_1, ..., u_k), (v_1, ..., v_k)) such that (u_i,v_i) in A(G) for i = 1, ..., k and (v_i, u_{i+1}) in A(G) for i = 1, ..., k-1. For every k we derive upper and lower bounds for the chromatic number of i_k(G) in terms of that of G. In particular, we find tight bounds on the chromatic number of interlacing adjoints of transitive tournaments. We use this result in conjunction with categorial properties of adjoint functors to derive the following consequence. For every integer ell, there exists a directed path Q_{ell} of algebraic length ell which admits homomorphisms into every directed graph of chromatic number at least 4. We discuss a possible impact of this approach on the multifactor version of the weak Hedetniemi conjecture.

Recommendations

• The interleaved multichromatic number of a graph
• On multiplicative graphs and the product conjecture
• scientific article; zbMATH DE number 37867
• scientific article; zbMATH DE number 2151258
• Adaptable chromatic number of graph products

Cites work

• scientific article; zbMATH DE number 37867 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• A Theorem on n-Coloring the Points of a Linear Graph
• A dualistic approach to bounding the chromatic number of a graph
• A survey on Hedetniemi's conjecture
• Adjoint functors and tree duality
• Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function
• Circular chromatic number: A survey
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Homomorphisms to oriented paths
• Nombre chromatique et plus longs chemins d'un graphe
• On classes of relations and graphs determined by subobjects and factorobjects
• On the arc-chromatic number of a digraph
• Path homomorphisms, graph colorings, and Boolean matrices
• Resource-sharing system scheduling and circular chromatic number
• The Categorical Product of Graphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The right adjoints into the categories of relational systems
• Zur algebraischen Begründung der Graphentheorie. I

Cited in

(2)

• The interleaved multichromatic number of a graph
• Hedetniemi's conjecture and adjoint functors in thin categories

This page was built for publication: Interleaved adjoints of directed graphs

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