Interleaved adjoints of directed graphs

DOI10.1016/J.EJC.2011.03.013zbMATH Open1292.05122arXiv0905.1200OpenAlexW2042465032MaRDI QIDQ648963FDOQ648963

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

Publication date: 29 November 2011

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

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.

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

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

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)

Cites Work

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

Cited In (2)

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

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)