Geodesic
Uniquely D-colourable Digraphs with Large Girth
Canadian journal of mathematics, Tome 64 (2012) no. 6, pp. 1310-1328

Voir la notice de l'article provenant de la source Cambridge University Press

Let $C$ and $D$ be digraphs. A mapping $f:V\left( D \right)\to V\left( C \right)$ is a $C$ -colouring if for every arc $uv$ of $D$ , either $f\left( u \right)f\left( v \right)$ is an arc of $C$ or $f\left( u \right)=f\left( v \right)$ , 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 $r\ge 1$ , there are uniquely circularly $r$ -colourable digraphs with arbitrarily large girth.
DOI : 10.4153/CJM-2011-084-9
Mots-clés : 05C15, 05C20, 60C05, digraph colouring, acyclic homomorphism, circular chromatic number, girth 
Harutyunyan, Ararat; Kayll, P. Mark; Mohar, Bojan; Rafferty, Liam. Uniquely D-colourable Digraphs with Large Girth. Canadian journal of mathematics, Tome 64 (2012) no. 6, pp. 1310-1328. doi: 10.4153/CJM-2011-084-9
@article{10_4153_CJM_2011_084_9,
     author = {Harutyunyan, Ararat and Kayll, P. Mark and Mohar, Bojan and Rafferty, Liam},
     title = {Uniquely {D-colourable} {Digraphs} with {Large} {Girth}},
     journal = {Canadian journal of mathematics},
     pages = {1310--1328},
     year = {2012},
     volume = {64},
     number = {6},
     doi = {10.4153/CJM-2011-084-9},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2011-084-9/}
}
TY  - JOUR
AU  - Harutyunyan, Ararat
AU  - Kayll, P. Mark
AU  - Mohar, Bojan
AU  - Rafferty, Liam
TI  - Uniquely D-colourable Digraphs with Large Girth
JO  - Canadian journal of mathematics
PY  - 2012
SP  - 1310
EP  - 1328
VL  - 64
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2011-084-9/
DO  - 10.4153/CJM-2011-084-9
ID  - 10_4153_CJM_2011_084_9
ER  - 
%0 Journal Article
%A Harutyunyan, Ararat
%A Kayll, P. Mark
%A Mohar, Bojan
%A Rafferty, Liam
%T Uniquely D-colourable Digraphs with Large Girth
%J Canadian journal of mathematics
%D 2012
%P 1310-1328
%V 64
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2011-084-9/
%R 10.4153/CJM-2011-084-9
%F 10_4153_CJM_2011_084_9

[1] [1] Aigner, M. and Ziegler, G. M., Proofs from The Book. Fourth ed. Springer-Verlag, Berlin, 2010. Google Scholar | DOI

[2] [2] Alon, N. and Spencer, J. H., The probabilistic method. Second ed. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. Google Scholar | DOI

[3] [3] Bang-Jensen, J. and Gutin, G., Digraphs. Theory, algorithms and applications. Second ed., Springer Monographs in Mathematics, Springer-Verlag, London, 2009. Google Scholar | DOI

[4] [4] Bokal, D., G. Fijavž, Juvan, M., Kayll, P. M., and Mohar, B., The circular chromatic number of a digraph. J. Graph Theory 46(2004), no. 3, 227–240. Google Scholar | DOI

[5] [5] Bollobás, B., Modern graph theory. Graduate Texts in Mathematics, 184, Springer-Verlag, New York, 1998. Google Scholar

[6] [6] Bollobás, B. and Sauer, N., Uniquely colourable graphs with large girth. Canad. J. Math. 28(1976), no. 6, 1340–1344. Google Scholar | DOI

[7] [7] Bondy, J. A. and Murty, U. S. R., Graph theory. Graduate Texts in Mathematics, 244, Springer, New York, 2008. Google Scholar | DOI

[8] [8] Descartes, B., A three-colour problem. Eureka 9 (April 1947), 21; solution in Eureka 10 (March 1948), 24–25. Google Scholar

[9] [9] Descartes, B., Solution to advanced problem no. 4526, proposed by P. Ungar. Amer. Math. Monthly 61(1954), no. 5, 352–353. Google Scholar | DOI

[10] [10] Diestel, R., Graph theory. Fourth ed., Graduate Texts in Mathematics, 173, Springer, Heidelberg, 2010. Google Scholar

[11] [11] Emden-Weinert, T., Hougardy, S., and Kreuter, B., Uniquely colourable graphs and the hardness of colouring graphs of large girth. Combin. Probab. Comput. 7(1998), no. 4, 375–386. Google Scholar | DOI

[12] [12] Erdʺos, P., Graph theory and probability. Canad. J. Math. 11(1959), 34–38. Google Scholar | DOI

[13] [13] Godsil, C. and Royle, G., Algebraic graph theory. Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001. Google Scholar

[14] [14] Harutyunyan, A., Brooks-type results for colouring of digraphs. Ph. D. dissertation, Simon Fraser University, 2011. Google Scholar

[15] [15] Hell, P. and Něsetřil, J., Graphs and homomorphisms. Oxford Lecture Series in Mathematics and its Applications, 28, Oxford University Press, Oxford, 2004. Google Scholar | DOI

[16] [16] Kelly, J. B. and Kelly, L. M., Paths and circuits in critical graphs. Amer. J. Math. 76(1954), 786–792. Google Scholar | DOI

[17] [17] Kostochka, A. V. and Něsetřil, J., Properties of Descartes’ construction of triangle-free graphs with high chromatic number. Combin. Probab. Comput. 8(1999), no. 5, 467–472. Google Scholar | DOI

[18] [18] Křıž, I., A hypergraph-free construction of highly chromatic graphs without short cycles. Combinatorica 9(1989), no. 2, 227–229. Google Scholar | DOI

[19] [19] Lin, S. and Zhu, X., Uniquely circular colourable and uniquely fractional colourable graphs of large girth. Contrib. Discrete Math. 1(2006), no. 1, 57–67 (electronic). Google Scholar

[20] [20] Lovász, L., On chromatic number of finite set-systems. Acta Math. Acad. Sci. Hungar. 19(1968), 59–67. Google Scholar | DOI

[21] [21] Mohar, B., Circular colorings of edge-weighted graphs. J. Graph Theory 43(2003), no. 2, 107–116. Google Scholar | DOI

[22] [22] Molloy, M. and Reed, B., Graph colouring and the probabilistic method. Algorithms and Combinatorics, 23, Springer-Verlag, Berlin, 2002. Google Scholar

[23] [23] Müller, V., On colorings of graphs without short cycles. Discrete Math. 26(1979), no. 2, 165–176. Google Scholar | DOI

[24] [24] Mycielski, J., Sur le coloriage des graphs. Colloq. Math. 3(1955), 161–162. Google Scholar

[25] [25] Něsetřil, J., On uniquely colorable graphs without short cycles. Časopis Pěst. Mat. 98(1973), 122–125, 212. Google Scholar

[26] [26] Něsetřil, J. and V. Rödl, A short proof of the existence of highly chromatic hypergraphs without short cycles. J. Combin. Theory Ser. B 27(1979), no. 2, 225–227. Google Scholar | DOI

[27] [27] Něsetřil, J. and Zhu, X., Construction of sparse graphs with prescribed circular colorings. Graph theory (Prague, 1998). Discrete Math. 233(2001), no. 1–3, 277–291. Google Scholar | DOI

[28] [28] Něsetřil, J. and Zhu, X., On sparse graphs with given colorings and homomorphisms. J. Combin. Theory Ser. B 90(2004), no. 1, 161–172. Google Scholar | DOI

[29] [29] Pan, Z. and Zhu, X., Graphs of large girth with prescribed partial circular colourings. Graphs Combin. 21(2005), no. 1, 119–129. Google Scholar | DOI

[30] [30] Rafferty, L., D-colorable digraphs with large girth. Ph. D. dissertation, University of Montana, 2011. Google Scholar

[31] [31] Zhu, X., Uniquely H-colorable graphs with large girth. J. Graph Theory 23(1996), no. 1, 33–41. Google Scholar | DOI

[32] [32] Zhu, X., Construction of uniquely H-colorable graphs. J. Graph Theory 30(1999), no. 1, 1–6. Google Scholar | DOI

[33] [33] Zhu, X., Circular chromatic number: a survey. Combinatorics, graph theory, algorithms and applications. Discrete Math. 229(2001), no. 1–3, 371–410. Google Scholar | DOI

[34] [34] Zykov, A. A., On some properties of linear complexes. (Russian) Mat. Sbornik N. S. (1949), 163–188; English translation in Amer. Math. Soc. Translation 1952(1952), no. 79, 33pp. Google Scholar

Cité par Sources :