D-colorable digraphs with large girth

<p>In 1959 Paul Erdos (<italic>Graph theory and probability</italic>, Canad. J. Math. <bold>11</bold> (1959), 34-38) famously proved, nonconstructively, that there exist graphs that have both arbitrarily large girth and arbitrarily large chromatic number. This result, along with its proof, has had a number of descendants (D. Bokal, G. Fijavz, M. Juvan, P.M. Kayll and B. Mohar, <italic>The circular chromatic number of a digraph</italic>, J. Graph Theory <bold>46</bold> (2004), 227-240; B. Bollobas and N. Sauer, <italic>Uniquely colourable graphs with large girth</italic>, Canad. J. Math. <bold>28</bold> (1976), 1340-1344; J. Nesetril and X. Zhu, <italic>On sparse graphs with given colorings and homomorphisms</italic>, J. Combin. Theory Ser. B <bold>90</bold> (2004), 161-172; X. Zhu, <italic>Uniquely H-colorable graphs with large girth</italic>, J. Graph Theory <bold>23</bold> (1996), 33-41) that have extended and generalized the result while strengthening the techniques used to achieve it. We follow the lead of Xuding Zhu (op. cit.) who proved that, for a suitable graph H, there exist graphs of arbitrarily large girth that are uniquely H-colorable. We establish an analogue of Zhu's results in a digraph setting.</p> <p>Let C and D be digraphs. A mapping f:V(D)&rarr V(C) is a C-coloring 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-colorable if it admits a C-coloring and that D is uniquely C-colorable if it is surjectively C-colorable and any two C-colorings of D differ by an automorphism of C. We prove that if D is a digraph that is not C-colorable, then there exist graphs of arbitrarily large girth that are D-colorable but not C-colorable. Moreover, for every digraph D that is uniquely D-colorable, there exists a uniquely D-colorable digraph of arbitrarily large girth.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Grantor dc:publisher

University of Montana

Year

2011

Author dc:creator

• Rafferty, Liam

• acyclic
• coloring
• digraph
• graph
• homomorphism

Repository record dc:identifier

https://scholarworks.umt.edu/etd/290

OAI identifier oai:identifier

oai:scholarworks.umt.edu:etd-1309