Interleaved adjoints on directed graphs

Details Interleaved adjoints on directed graphs Interleaved adjoints on directed graphs

2009-05-08

arxiv.org/abs/0905.1200v2

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Interleaved adjoints on directed graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Interleaved adjoints on directed graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaved adjoints on directed graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-703335