×

Colourings, homomorphisms, and partitions of transitive digraphs. (English) Zbl 1348.05073

Summary: We investigate the complexity of generalizations of colourings (acyclic colourings, \((k, \ell)\)-colourings, homomorphisms, and matrix partitions), for inputs restricted to the class of transitive digraphs. Even though transitive digraphs are nicely structured, many problems are intractable, and their complexity turns out to be difficult to classify. We present some motivational results and several open problems.

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2000), Springer-Verlag
[2] Bang-Jensen, J.; Huang, J., Quasi-transitive digraphs, J. Graph Theory, 20, 141-161 (1995) · Zbl 0832.05048
[3] Bang-Jensen, J.; MacGillivray, G.; Swarts, J., The complexity of colouring by locally semicomplete digraphs, Discrete Math., 310, 2675-2684 (2010) · Zbl 1221.05173
[4] Chudnovsky, M., Berge trigraphs, J. Graph Theory, 55, 1-55 (2006) · Zbl 1101.05036
[5] Dinneen, M. J.; Lai, R., Properties of vertex cover obstructions, Discrete Math., 307, 2484-2500 (2007) · Zbl 1128.05042
[6] Dinneen, M. J.; Xiong, L., Minor-order obstructions for the graphs of vertex cover 6, J. Graph Theory, 41, 163-178 (2002) · Zbl 1012.05145
[7] Ekim, T.; Gimbel, J., Partitioning graphs into complete and empty graphs, Discrete Math., 309, 5849-5856 (2009) · Zbl 1186.05095
[8] Feder, T.; Hell, P., Matrix partitions of perfect graphs, Discrete Math., 306, 2450-2460 (2006) · Zbl 1143.05035
[9] Feder, T.; Hell, P., On realizations of point determining graphs, and obstructions to full homomorphisms, Discrete Math., 308, 1639-1652 (2008) · Zbl 1135.05042
[10] Feder, T.; Hell, P.; Hernández-Cruz, C., Colourings, homomorphisms, and partitions of transitive digraphs · Zbl 1348.05073
[11] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 449-478 (2003) · Zbl 1029.05143
[12] Feder, T.; Hell, P.; Tucker-Nally, K., Digraph matrix partitions and trigraph homomorphisms, Discrete Appl. Math., 154, 2458-2469 (2006) · Zbl 1106.05060
[13] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Comput., 28, 236-250 (1998) · Zbl 0914.68075
[14] Galeana-Sánchez, H.; Hernández-Cruz, C., \(k\)-kernels in generalizations of transitive digraphs, Discuss. Math. Graph Theory, 31, 293-312 (2011) · Zbl 1234.05113
[15] Golovach, P. A.; Johnson, M.; Paulusma, D.; Song, J., A survey on the computational complexity of colouring graphs with forbidden subgraphs, J. Graph Theory (2016), in press
[16] Golumbic, M., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press · Zbl 0541.05054
[17] Hell, P., Graph partitions with prescribed patterns, European J. Combin., 35, 335-353 (2014) · Zbl 1292.05214
[18] Keevash, P.; Li, Z.; Mohar, B.; Reed, B., Digraph girth via chromatic number, SIAM J. Discrete Math., 27, 639-696 (2013) · Zbl 1272.05065
[19] Neumann-Lara, V., The dichromatic number of a digraph, J. Combin. Theory Ser. B, 33, 265-270 (1982) · Zbl 0506.05031
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.