Uniquely D-colourable digraphs with large girth

DOI10.4153/CJM-2011-084-9zbMATH Open1254.05057arXiv1109.5208OpenAlexW1999197342MaRDI QIDQ3143310FDOQ3143310

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

Publication date: 29 November 2012

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

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.

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

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

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)

Cited In (12)

• Uniquely colourable m-dichromatic oriented graphs
• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• Extension of Gyárfás-Sumner conjecture to digraphs
• On the Complexity of Digraph Colourings and Vertex Arboricity
• Title not available (Why is that?)
• Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization
• Digraph coloring and distance to acyclicity
• Title not available (Why is that?)
• Subgraphs of Kneser graphs with large girth and large chromatic number
• Results on uniquely colorable digraphs
• Uniquely circular colourable and uniquely fractional colourable graphs of large girth
• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth

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)