Interleaved adjoints of directed graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10104489" target="_blank" >RIV/00216208:11320/11:10104489 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.ejc.2011.03.013" target="_blank" >http://dx.doi.org/10.1016/j.ejc.2011.03.013</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ejc.2011.03.013" target="_blank" >10.1016/j.ejc.2011.03.013</a>

Result language
angličtina
Original language name
Interleaved adjoints of directed graphs
Original language description
For an integer k }= 1, the kth interleaved adjoint of a digraph G is the digraph l(k)(G) with vertex-set V(G)(k), and arcs ((u(1), ... ,u(k)). (v(1), ... , v(k))) such that (u(i), v(i)) is an element of A(G) for i = 1, ... , k and (v(i), u(i+1)) is an element of A(G) for i = 1, ... , k - 1. For every k, we derive upper and lower bounds for the chromatic number of l(k)(G) in terms of that of G. In the case where G is a transitive tournament, the exact value of the chromatic number of l(k)(G) has been determined by [H.G. Yeh, X. Zhu, Resource-sharing system scheduling and circular chromatic number, Theoret. Comput. Sci. 332 (2005) 447-460]. We use the latter result in conjunction with categorical properties of adjoint functors to derive the following consequence. For every integer l, there exists a directed path Q(l) of algebraic length l which admits homomorphisms into every directed graph of chromatic number at least 4. We discuss a possible impact of this approach on the multifactor v
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)