Complete edge-colored permutation graphs. (English) Zbl 1491.05080
Summary: We introduce the concept of complete edge-colored permutation graphs as complete graphs that are the edge-disjoint union of “classical” permutation graphs. We show that a graph \(G = (V, E)\) is a complete edge-colored permutation graph if and only if each monochromatic subgraph of \(G\) is a “classical” permutation graph and \(G\) does not contain a triangle with 3 different colors. Using the modular decomposition as a framework we demonstrate that complete edge-colored permutation graphs are characterized in terms of their strong prime modules, which induce also complete edge-colored permutation graphs. This leads to an \(\mathcal{O}(| V |^2)\)-time recognition algorithm. We show, moreover, that complete edge-colored permutation graphs form a superclass of so-called symbolic ultrametrics and that the coloring of such graphs is always a Gallai coloring.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05A05 | Permutations, words, matrices |
| 05A18 | Partitions of sets |
| 05A19 | Combinatorial identities, bijective combinatorics |
| 05C72 | Fractional graph theory, fuzzy graph theory |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C90 | Applications of graph theory |
Keywords:
permutation graph; \(k\)-edge-coloring; modular decomposition; symbolic ultrametric; cograph; Gallai coloringReferences:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., On finding lowest common ancestors in trees, SIAM J. Comput., 5, 115-132 (1976) · Zbl 0325.68018 |
| [2] | Aldous, D.; Diaconis, P., Shuffling cards and stopping times, Am. Math. Mon., 93, 333-348 (1986) · Zbl 0603.60006 |
| [3] | Baker, K. A.; Fishburn, P. C.; Roberts, F. S., Partial orders of dimension 2, Networks, 2, 11-28 (1972) · Zbl 0247.06002 |
| [4] | Ball, R. N.; Pultr, A.; Vojtěchovskỳ, P., Colored graphs without colorful cycles, Combinatorica, 27, 407-427 (2007) · Zbl 1174.05041 |
| [5] | Balogh, J.; Li, L., The typical structure of Gallai colorings and their extremal graphs, SIAM J. Discrete Math., 33, 2416-2443 (2018) · Zbl 1428.05094 |
| [6] | Bastos, J. de O.; Benevides, F. S.; Han, J., The number of Gallai k-colorings of complete graphs, J. Comb. Theory, Ser. B, 144, 1-13 (2020) · Zbl 1443.05060 |
| [7] | Bastos, J. de O.; Benevides, F. S.; Mota, G. O.; Sau, I., Counting Gallai 3-colorings of complete graphs, Discrete Math., 342, 2618-2631 (2019) · Zbl 1416.05098 |
| [8] | Bergeron, A.; Chauve, C.; De Montgolfier, F.; Raffinot, M., Computing common intervals of k permutations, with applications to modular decomposition of graphs, SIAM J. Discrete Math., 22, 1022-1039 (2008) · Zbl 1190.05044 |
| [9] | Bhatia, S.; Feijão, P.; Francis, A. R., Position and content paradigms in genome rearrangements: the wild and crazy world of permutations in genomics, Bull. Math. Biol., 80, 3227-3246 (2018) · Zbl 1404.92126 |
| [10] | Böcker, S.; Dress, A. W., Recovering symbolically dated, rooted trees from symbolic ultrametrics, Adv. Math., 138, 105-125 (1998) · Zbl 0912.05031 |
| [11] | Bodlaender, H. L., Achromatic number is NP-complete for cographs and interval graphs, Inf. Process. Lett., 31, 135-138 (1989) · Zbl 0684.68046 |
| [12] | Bóna, M., Combinatorics of Permutations (2016), Chapman and Hall/CRC |
| [13] | Bose, P.; Buss, J. F.; Lubiw, A., Pattern matching for permutations, Inf. Process. Lett., 65, 277-283 (1998) · Zbl 1338.68304 |
| [14] | Brandstädt, A.; Kratsch, D., On the restriction of some NP-complete graph problems to permutation graphs, (Proc. Fundamentals of Computation Theory. Proc. Fundamentals of Computation Theory, FCT 1985 (1985), Springer), 53-62 · Zbl 0575.68069 |
| [15] | Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph Classes: A Survey (1999), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 0919.05001 |
| [16] | Cameron, K.; Edmonds, J., Lambda composition, J. Graph Theory, 26, 9-16 (1997) · Zbl 0878.05065 |
| [17] | Capelle, C.; Habib, M.; Montgolfier, F., Graph decompositions and factorizing permutations, Discrete Math. Theor. Comput. Sci., 5, 55-70 (2002) · Zbl 0994.68095 |
| [18] | Corneil, D. G.; Lerchs, H.; Burlingham, L. S., Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057 |
| [19] | Crespelle, C.; Paul, C., Fully dynamic algorithm for recognition and modular decomposition of permutation graphs, Algorithmica, 58, 405-432 (2010) · Zbl 1205.68258 |
| [20] | Deogun, J. S.; Steiner, G., Polynomial algorithms for Hamiltonian cycle in cocomparability graphs, SIAM J. Comput., 23, 520-552 (1994) · Zbl 0811.05043 |
| [21] | Dushnik, B.; Miller, E. W., Partially ordered sets, Am. J. Math., 63, 600-610 (1941) · JFM 67.0157.01 |
| [22] | Ehrenfeucht, A.; Gabow, H. N.; Mcconnell, R. M.; Sullivan, S. J., An \(\mathcal{O}( n^2)\) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs, J. Algorithms, 16, 283-294 (1994) · Zbl 0797.68079 |
| [23] | Ehrenfeucht, A.; Harju, T.; Rozenberg, G., The Theory of 2-Structures: A Framework for Decomposition and Transformation of Graphs (1999), World Scientific: World Scientific Singapore · Zbl 0981.05002 |
| [24] | Ehrenfeucht, A.; Rozenberg, G., Partial (set) 2-structures, Acta Inform., 27, 343-368 (1990) · Zbl 0696.68083 |
| [25] | Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, part I: clans, basic subclasses, and morphisms, Theor. Comput. Sci., 70, 277-303 (1990) · Zbl 0701.05051 |
| [26] | Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, part II: representation through labeled tree families, Theor. Comput. Sci., 70, 305-342 (1990) · Zbl 0701.05052 |
| [27] | Engelfriet, J.; Harju, T.; Proskurowski, A.; Rozenberg, G., Characterization and complexity of uniformly nonprimitive labeled 2-structures, Theor. Comput. Sci., 154, 247-282 (1996) · Zbl 0873.68161 |
| [28] | Erdős, P.; Simonovits, M.; Sós, V. T., Anti-Ramsey theorems, (Infinite and Finite Sets, vol. II (1973)), 633-643 · Zbl 0316.05111 |
| [29] | Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S., Combinatorics of Genome Rearrangements (2009), MIT Press · Zbl 1170.92022 |
| [30] | Fujita, S.; Magnant, C.; Ozeki, K., Rainbow generalizations of Ramsey theory: a survey, Graphs Comb., 26, 1-30 (2010) · Zbl 1231.05178 |
| [31] | Gallai, T., Transitiv orientierbare graphen, Acta Math. Hung., 18, 25-66 (1967) · Zbl 0153.26002 |
| [32] | Golovach, P. A.; Heggernes, P.; Mihai, R., Edge search number of cographs, Discrete Appl. Math., 160, 734-743 (2012) · Zbl 1238.68107 |
| [33] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, vol. 57 (2004), Elsevier · Zbl 1050.05002 |
| [34] | Golumbic, M. C.; Rotem, D.; Urrutia, J., Comparability graphs and intersection graphs, Discrete Math., 43, 37-46 (1983) · Zbl 0502.05050 |
| [35] | Gyárfás, A., Large monochromatic components in edge colorings of graphs: a survey, (Ramsey Theory (2011), Springer), 77-96 · Zbl 1221.05140 |
| [36] | Gyárfás, A.; Pálvölgyi, D.; Patkós, B.; Wales, M., Distribution of colors in Gallai colorings, Eur. J. Comb., 86, Article 103087 pp. (2020) · Zbl 1437.05072 |
| [37] | Gyárfás, A.; Sárközy, G. N., Gallai colorings of non-complete graphs, Discrete Math., 310, 977-980 (2010) · Zbl 1230.05128 |
| [38] | Gyárfás, A.; Sárközy, G. N.; Sebő, A.; Selkow, S., Ramsey-type results for Gallai colorings, J. Graph Theory, 64, 233-243 (2010) · Zbl 1209.05082 |
| [39] | Gyárfás, A.; Simony, G., Edge colorings of complete graphs without tricolored triangles, J. Graph Theory, 46, 211-216 (2004) · Zbl 1041.05028 |
| [40] | Habib, M.; Paul, C., A survey of the algorithmic aspects of modular decomposition, Comput. Sci. Rev., 4, 41-59 (2010) · Zbl 1302.68140 |
| [41] | Harel, D.; Tarjan, R. E., Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 338-355 (1984) · Zbl 0535.68022 |
| [42] | Hartmann, T.; Middendorf, M.; Bernt, M., Genome rearrangement analysis: cut and join genome rearrangements and gene cluster preserving approaches, (Comparative Genomics (2018), Springer), 261-289 |
| [43] | Hellmuth, M.; Hernandez-Rosales, M.; Huber, K. T.; Moulton, V.; Stadler, P. F.; Wieseke, N., Orthology relations, symbolic ultrametrics, and cographs, J. Math. Biol., 66, 399-420 (2013) · Zbl 1408.05038 |
| [44] | Hellmuth, M.; Stadler, P.; Wieseke, N., The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations, J. Math. Biol., 75, 199-237 (2017) · Zbl 1368.05023 |
| [45] | Hellmuth, M.; Wieseke, N., From sequence data including orthologs, paralogs, and xenologs to gene and species trees, (Evolutionary Biology: Convergent Evolution, Evolution of Complex Traits, Concepts and Methods (2016), Springer International), 373-392 |
| [46] | Hellmuth, M.; Wieseke, N., On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions, J. Comb. Optim., 36, 591-616 (2018) · Zbl 1402.90147 |
| [47] | Hellmuth, M.; Wieseke, N.; Lechner, M.; Lenhof, H. P.; Middendorf, M.; Stadler, P. F., Phylogenomics with paralogs, Proc. Natl. Acad. Sci. USA, 112, 2058-2063 (2015) |
| [48] | Kano, M.; Li, X., Monochromatic and heterochromatic subgraphs in edge-colored graphs – a survey, Graphs Comb., 24, 237-263 (2008) · Zbl 1190.05045 |
| [49] | Kim, H., Finding a maximum independent set in a permutation graph, Inf. Process. Lett., 36, 19-23 (1990) · Zbl 0703.68062 |
| [50] | Koh, Y.; Ree, S., Connected permutation graphs, Discrete Math., 307, 2628-2635 (2007) · Zbl 1126.05058 |
| [51] | Körner, J.; Simonyi, G.; Tuza, Z., Perfect couples of graphs, Combinatorica, 12, 179-192 (1992) · Zbl 0778.05071 |
| [52] | Lafond, M.; El-Mabrouk, N., Orthology and paralogy constraints: satisfiability and consistency, BMC Genomics, 15, S12 (2014) |
| [53] | McConnell, R. M.; Spinrad, J. P., Modular decomposition and transitive orientation, Discrete Math., 201, 189-241 (1999) · Zbl 0933.05146 |
| [54] | Möhring, R. F.; Radermacher, F. J., Substitution decomposition for discrete structures and connections with combinatorial optimization, (Algebraic and Combinatorial Methods in Operations Research. Algebraic and Combinatorial Methods in Operations Research, North-Holland. Algebraic and Combinatorial Methods in Operations Research. Algebraic and Combinatorial Methods in Operations Research, North-Holland, North-Holland Mathematics Studies, vol. 95 (1984)) · Zbl 0567.90073 |
| [55] | Möhring, R. H., Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions, Ann. Oper. Res., 4, 195-225 (1985) |
| [56] | Pnueli, A.; Lempel, A.; Even, S., Transitive orientation of graphs and identification of permutation graphs, Can. J. Math., 23, 160-175 (1971) · Zbl 0204.24604 |
| [57] | Seinsche, D., On a property of the class of n-colorable graphs, J. Comb. Theory, Ser. B, 16, 191-193 (1974) · Zbl 0269.05103 |
| [58] | Semple, C.; Steel, M., Phylogenetics (2003), Oxford University Press · Zbl 1043.92026 |
| [59] | Wagner, K., Monotonic coverings of finite sets, J. Inf. Process. Cybern., 20, 633-639 (1984) · Zbl 0566.68041 |
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.
