×

Digraph matrix partitions and trigraph homomorphisms. (English) Zbl 1106.05060

Summary: Matrix partitions generalize graph colourings and homomorphisms. Their study has so far been confined to symmetric matrices and undirected graphs. In this paper we make an initial study of list matrix partitions for digraphs; in other words our matrices are not necessarily symmetric. We motivate future conjectures by classifying the complexity of all list matrix partition problems for matrices of size up to three. We find it convenient to model the problem in the language of trigraph homomorphisms.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Marshall, T. H., Homomorphisms of edge-colored graphs, and Coxeter groups, J. Algebraic Combin., 8, 5-13 (1998) · Zbl 0911.05034
[2] Bang-Jansen, J.; Hell, P.; MacGillivray, G., The complexity of colourings by semicomplete digraphs, SIAM J. Discrete Math., 1, 281-289 (1988) · Zbl 0678.05018
[3] R.C. Brewster, Edge-coloured vertex colourings, Ph.D. Thesis, Simon Fraser University, 1993.; R.C. Brewster, Edge-coloured vertex colourings, Ph.D. Thesis, Simon Fraser University, 1993.
[4] R.C. Brewster, R. Dedić, F. Huard, J. Queen, Edge-coloured homomorphisms and bound quivers recognition, Discrete Math., to appear.; R.C. Brewster, R. Dedić, F. Huard, J. Queen, Edge-coloured homomorphisms and bound quivers recognition, Discrete Math., to appear. · Zbl 1070.05036
[5] A.A. Bulatov, Tractable conservative constraint satisfaction problems, Tech Report ,Oxford University Computing Laboratory, PRG-RR-03-01.; A.A. Bulatov, Tractable conservative constraint satisfaction problems, Tech Report ,Oxford University Computing Laboratory, PRG-RR-03-01. · Zbl 1351.68113
[6] K. Cameron, E.M. Eschen, C. Hoang, R. Sritharan, The complexity of the list partition problem for graphs, SODA 2004.; K. Cameron, E.M. Eschen, C. Hoang, R. Sritharan, The complexity of the list partition problem for graphs, SODA 2004. · Zbl 1151.05045
[7] Dantas, S.; de Figueiredo, C. M.H.; Klein, S.; Gravier, S.; Reed, B., Stable skew partition problem, Discrete Appl. Math., 143, 17-22 (2004) · Zbl 1053.05058
[8] de Figueiredo, C. M.H.; Klein, S., The NP-completeness of multipartite cutset testing, Congr. Numer., 119, 217-222 (1996) · Zbl 0897.68070
[9] de Figueiredo, C. M.H.; Klein, S.; Kohayakawa, Y.; Reed, B., Finding skew partitions efficiently, J. Algorithms, 37, 505-521 (2000) · Zbl 0964.68107
[10] T. Feder, P. Hell, Full constraint satisfaction problems, SIAM J. Comput., in press.; T. Feder, P. Hell, Full constraint satisfaction problems, SIAM J. Comput., in press. · Zbl 1111.68115
[11] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033
[12] T. Feder, P. Hell, J. Huang, List homomorphisms to reflexive digraphs, manuscript 2005.; T. Feder, P. Hell, J. Huang, List homomorphisms to reflexive digraphs, manuscript 2005. · Zbl 1236.05092
[13] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 449-478 (2003) · Zbl 1029.05143
[14] T. Feder, P. Hell, S. Klein, R. Motwani, Complexity of graph partition problems, 31st Annual ACM STOC, 1999, pp. 464-472.; T. Feder, P. Hell, S. Klein, R. Motwani, Complexity of graph partition problems, 31st Annual ACM STOC, 1999, pp. 464-472. · Zbl 1345.68171
[15] T. Feder, P. Hell, S. Klein, L. T. Nogueira, F. Protti, List matrix partitions of chordal graphs, Theor. Comput. Sci. 349 (2005) 52-66.; T. Feder, P. Hell, S. Klein, L. T. Nogueira, F. Protti, List matrix partitions of chordal graphs, Theor. Comput. Sci. 349 (2005) 52-66. · Zbl 1084.05026
[16] T. Feder, P. Hell, D. \(Král^{′;}\); T. Feder, P. Hell, D. \(Král^{′;}\)
[17] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction, SIAM J. Comput., 28, 57-104 (1998) · Zbl 0914.68075
[18] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[19] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[20] W. Gutjahr, Graph colourings, Ph.D. Thesis, Freie Universität Berlin, 1991.; W. Gutjahr, Graph colourings, Ph.D. Thesis, Freie Universität Berlin, 1991.
[21] W. Gutjahr, E. Welzl, G. Woeginger, Polynomial graph-colorings, STACS 89, Lecture Notes in Computer Science, vol. 349, Springer,Berlin, 1989, pp. 108-119.; W. Gutjahr, E. Welzl, G. Woeginger, Polynomial graph-colorings, STACS 89, Lecture Notes in Computer Science, vol. 349, Springer,Berlin, 1989, pp. 108-119. · Zbl 0761.05040
[22] Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph-colorings, Discrete Appl. Math., 35, 29-45 (1992) · Zbl 0761.05040
[23] P. Hell, Algorithmic aspects of graph homomorphisms, in: C.D. Wensley (Ed.), Surveys in Combinatorics 2003, London Mathematical Society Lecture Note Series, vol. 307, 2003, pp. 239-276.; P. Hell, Algorithmic aspects of graph homomorphisms, in: C.D. Wensley (Ed.), Surveys in Combinatorics 2003, London Mathematical Society Lecture Note Series, vol. 307, 2003, pp. 239-276. · Zbl 1035.05089
[24] Hell, P.; Klein, S.; Tito Nogueira, L.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Appl. Math., 141, 185-194 (2004) · Zbl 1043.05097
[25] Hell, P.; Nešetřil, J., On the complexity of \(H\)-coloring, J. Combin. Theory Ser. B, 48, 92-110 (1990) · Zbl 0639.05023
[26] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press: Oxford University Press New York · Zbl 1062.05139
[27] Jeavons, P. G., On the algebraic structure of combinatorial problems, Theoret. Comput. Sci., 200, 185-204 (1998) · Zbl 0915.68074
[28] Maurer, H. A.; Sudborough, J. H.; Welzl, E., On the complexity of the general colouring problem, Inform. and Control, 51, 123-145 (1981) · Zbl 0502.68015
[29] H Papadimitriou, C.; Steiglitz, K., Combinatorial Optimization (1982), Prentice-Hall: Prentice-Hall New York · Zbl 0503.90060
[30] K. Tucker-Nally, List M-partitions of digraphs, M.Sc. Thesis, Simon Fraser University, School of Computing Science, 2003.; K. Tucker-Nally, List M-partitions of digraphs, M.Sc. Thesis, Simon Fraser University, School of Computing Science, 2003.
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.