Uniquely D-colourable digraphs with large girth

DOI10.4153/CJM-2011-084-9MaRDI QIDQ3143310zbMATH OpenOpenAlexFDO

Authors Ararat Harutyunyan, P. Mark Kayll, Bojan Mohar, Liam Rafferty

Publication date 29 November 2012

Published in Canadian Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

uniquely circularly \(r\)-colourable digraphs\(C\)-colouring

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Abstract: Let C and D be digraphs. A mapping $f:V(D)oV(C)$ is a C-colouring if for every arc $uv$ of D, either $f(u)f(v)$ is an arc of C or $f(u)=f(v)$, and the preimage of every vertex of C induces an acyclic subdigraph in D. We say that D is C-colourable if it admits a C-colouring and that D is uniquely C-colourable if it is surjectively C-colourable and any two C-colourings of D differ by an automorphism of C. We prove that if a digraph D is not C-colourable, then there exist digraphs of arbitrarily large girth that are D-colourable but not C-colourable. Moreover, for every digraph D that is uniquely D-colourable, there exists a uniquely D-colourable digraph of arbitrarily large girth. In particular, this implies that for every rational number $rgeq1$, there are uniquely circularly r-colourable digraphs with arbitrarily large girth.

Recommendations

• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
• Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization
• Uniquely circular colourable and uniquely fractional colourable graphs of large girth
• A note on coloring digraphs of large girth
• scientific article; zbMATH DE number 927067

Cited in

(12)

• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• On the complexity of digraph colourings and vertex arboricity
• Extension of Gyárfás-Sumner conjecture to digraphs
• Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization
• Results on uniquely colorable digraphs
• Digraph coloring and distance to acyclicity
• Subgraphs of Kneser graphs with large girth and large chromatic number
• On colouring oriented graphs of large girth
• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
• Uniquely circular colourable and uniquely fractional colourable graphs of large girth
• Uniquely colourable m-dichromatic oriented graphs
• scientific article; zbMATH DE number 927067 (Why is no real title available?)

This page was built for publication: Uniquely \(D\)-colourable digraphs with large girth

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