×

Coloring digraphs with forbidden cycles. (English) Zbl 1319.05050

Summary: Let \(k\) and \(r\) be two integers with \(k\geq 2\) and \(k\geq r\geq 1\). In this paper we show that (1) if a strongly connected digraph \(D\) contains no directed cycle of length 1 modulo \(k\), then \(D\) is \(k\)-colorable; and (2) if a digraph \(D\) contains no directed cycle of length \(r\) modulo \(k\), then \(D\) can be vertex-colored with \(k\) colors so that each color class induces an acyclic subdigraph in \(D\). Our results give affirmative answers to two questions posed by Zs. Tuza [J. Comb. Theory, Ser. B 55, No. 2, 236–243 (1992; Zbl 0709.05019)]. Moreover, the second one implies the following strong form of a conjecture of A. A. Diwan et al. [Combinatorica 33, No. 3, 319–334 (2013; Zbl 1313.05115)]: If an undirected graph \(G\) contains no cycle of length \(r\) modulo \(k\), then \(G\) is \(k\)-colorable if \(r\neq 2\) and \((k+1)\)-colorable otherwise. Our results also strengthen several classical theorems on graph coloring proved by J. A. Bondy [J. Lond. Math. Soc., II. Ser. 14, 277–282 (1976; Zbl 0344.05124)], P. Erdős and A. Hajnal [“On chromatic numbers of graphs and set-systems”, Acta Math. Hung. 17, No. 1–2, 61–69 (1966; doi:10.1007/BF02020444], T. Gallai [in: Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 115–118 (1968; Zbl 0159.54403)] and B. Roy [Rev. Franç. Inform. Rech. Opér. 1, No. 5, 129–132 (1967; Zbl 0157.31302)], A. Gyárfás [Discrete Math. 103, No. 1, 41–48 (1992; Zbl 0773.05072)], etc.

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Berger, E.; Choromanski, K.; Chudnovsky, M.; Fox, J.; Loebl, M.; Scott, A.; Seymour, P.; Thomassé, S., Tournaments and coloring, J. Combin. Theory Ser. B, 103, 1-20 (2013) · Zbl 1254.05064
[2] Bokal, D.; Fijavž, G.; Juvan, M.; Kayll, P. M.; Mohar, B., The circular chromatic number of a digraph, J. Graph Theory, 46, 227-240 (2004) · Zbl 1041.05026
[3] Bondy, J. A., Diconnected orientations and a conjecture of Las Vergnas, J. Lond. Math. Soc., 14, 277-282 (1976) · Zbl 0344.05124
[4] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer · Zbl 1134.05001
[5] Chen, X.; Hu, X.; Zang, W., A min-max theorem on tournaments, SIAM J. Comput., 37, 923-937 (2007) · Zbl 1191.90028
[6] Dean, N.; Lesniak, L.; Saito, A., Cycles of length 0 modulo 4 in graphs, Discrete Math., 121, 37-49 (1993) · Zbl 0791.05064
[7] Diwan, A. A.; Kenkre, S.; Vishwanathan, S., Circumference, chromatic number and online coloring, Combinatorica, 33, 319-334 (2013) · Zbl 1313.05115
[8] Erdős, P., Problems and results in number theory and graph theory, Congr. Numer., XXVII, 3-21 (1980)
[9] Erdős, P.; Hajnal, A., On chromatic numbers of graphs and set systems, Acta Math. Sci. Hungar., 17, 61-99 (1966) · Zbl 0151.33701
[10] Gallai, T., On directed paths and circuits, (Erdős, P.; Katona, G. O.H., Theory of Graphs (1968), Academic Press: Academic Press San Diego), 115-118 · Zbl 0159.54403
[11] Golowich, N., Acyclic colorings of directed graphs (2014)
[12] Gyárfás, A., Graphs with \(k\) odd cycle lengths, Discrete Math., 103, 41-48 (1992) · Zbl 0773.05072
[13] Harutyunyan, A.; Mohar, B., Gallai’s theorem for list coloring of digraphs, SIAM J. Discrete Math., 25, 170-180 (2011) · Zbl 1330.05068
[14] Harutyunyan, A.; Mohar, B., Strengthened Brooks’ theorem for digraphs of girth at least three, Electron. J. Combin., 18 (2011), #P195 · Zbl 1230.05129
[15] Harutyunyan, A.; Mohar, B., Two results on the digraph chromatic number, Discrete Math., 312, 1823-1826 (2012) · Zbl 1242.05095
[16] Keevash, P.; Li, Z.; Mohar, B.; Reed, B., Digraph girth via chromatic number, SIAM J. Discrete Math., 27, 693-696 (2013) · Zbl 1272.05065
[17] Kenkre, S.; Vishwanathan, S., A bound on the chromatic number using the longest odd cycle length, J. Graph Theory, 54, 267-276 (2007) · Zbl 1120.05030
[18] Löwenstein, Ch.; Rautenbach, D.; Schiermeyer, I., Cycle length parities and the chromatic number, J. Graph Theory, 64, 210-218 (2010) · Zbl 1209.05091
[19] Mihók, P.; Schiermeyer, I., Cycle lengths and chromatic number of graphs, Discrete Math., 286, 147-149 (2004) · Zbl 1055.05060
[20] Mohar, B., Circular colorings of edge-weighted graphs, J. Graph Theory, 43, 107-116 (2003) · Zbl 1014.05026
[21] Neumann-Lara, V., The dichromatic number of a digraph, J. Combin. Theory Ser. B, 33, 265-270 (1982) · Zbl 0506.05031
[22] Roy, B., Nombre chromatique et plus longs chemins d’un graphe, Rev. Fr. Inform. Rech. Oper., 1, 129-132 (1967) · Zbl 0157.31302
[23] Tuza, Zs., Graph coloring in linear time, J. Combin. Theory Ser. B, 55, 236-243 (1992) · Zbl 0709.05019
[24] Tuza, Zs., Problems on cycles and colorings, Discrete Math., 313, 2007-2013 (2013) · Zbl 1277.05074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.