Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey

DOI10.1007/s00373-008-0789-5zbMath1190.05045OpenAlexW2026043319WikidataQ105583341 ScholiaQ105583341MaRDI QIDQ1014813

Mikio Kano, Xue Liang Li

Publication date: 29 April 2009

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-008-0789-5

Mathematics Subject Classification ID

Trees (05C05) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02)

Related Items (68)

Large Rainbow Matchings in Edge-Coloured Graphs ⋮ Vertex covers by monochromatic pieces -- a survey of results and problems ⋮ Assessing the Computational Complexity of Multi-layer Subgraph Detection ⋮ Rainbow triangles in arc-colored digraphs ⋮ Edge-disjoint rainbow spanning trees in complete graphs ⋮ Rainbow Ramsey simple structures ⋮ A generalization of heterochromatic graphs and \(f\)-chromatic spanning forests ⋮ Complexity results for rainbow matchings ⋮ Color degree sum conditions for rainbow triangles in edge-colored graphs ⋮ Rainbow number of matchings in planar graphs ⋮ Maximum properly colored trees in edge-colored graphs ⋮ Monochromatic loose path partitions in \(k\)-uniform hypergraphs ⋮ Color-line and proper color-line graphs ⋮ Rainbow generalizations of Ramsey theory: A survey ⋮ Rainbow edge-coloring and rainbow domination ⋮ Cover \(k\)-uniform hypergraphs by monochromatic loose paths ⋮ Extremal coloring for the anti-Ramsey problem of matchings in complete graphs ⋮ A note on heterochromatic \(C_4\) in edge-colored triangle-free graphs ⋮ Complete edge-colored permutation graphs ⋮ Anti-Ramsey numbers for matchings in regular bipartite graphs ⋮ On an anti-Ramsey threshold for random graphs ⋮ Rainbow path and color degree in edge colored graphs ⋮ On sufficient conditions for rainbow cycles in edge-colored graphs ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ Heterochromatic tree partition problem in complete tripartite graphs ⋮ Long rainbow paths and rainbow cycles in edge colored graphs. A survey ⋮ Edge-disjoint properly colored cycles in edge-colored complete graphs ⋮ Anti-Ramsey number of matchings in outerplanar graphs ⋮ Forbidden rainbow subgraphs that force large monochromatic or multicolored \(k\)-connected subgraphs ⋮ Rainbow cycles in edge-colored graphs ⋮ Long properly colored cycles in edge colored complete graphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Anti-Ramsey numbers for matchings in 3-regular bipartite graphs ⋮ Anti-Ramsey number of matchings in a hypergraph ⋮ Symbolic coloured SCC decomposition ⋮ Rainbow Perfect Matchings in Complete Bipartite Graphs: Existence and Counting ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ Rainbow matchings in edge-colored complete split graphs ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Anti-Ramsey coloring for matchings in complete bipartite graphs ⋮ Heterochromatic tree partition number in complete multipartite graphs ⋮ Existence of rainbow matchings in properly edge-colored graphs ⋮ A Dirac Type Condition for Properly Coloured Paths and Cycles ⋮ Properly colored \(C_4\)'s in edge-colored graphs ⋮ A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs ⋮ Unnamed Item ⋮ Properly colored spanning trees in edge-colored graphs ⋮ Unnamed Item ⋮ Rainbow triangles in edge-colored Kneser graphs ⋮ Some rainbow cycles in \(r\)-good edge-colorings ⋮ Rainbow cliques in edge-colored graphs ⋮ On heterochromatic out-directed spanning trees in tournaments ⋮ Rainbow triangles in arc-colored tournaments ⋮ Anti-Ramsey number of triangles in complete multipartite graphs ⋮ A note on large rainbow matchings in edge-coloured graphs ⋮ A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem ⋮ Quadratic vertex kernel for rainbow matching ⋮ Transversals in generalized Latin squares ⋮ Maximum colored trees in edge-colored graphs ⋮ On s-t paths and trails in edge-colored graphs ⋮ Rainbow edge-pancyclicity of strongly edge-colored graphs ⋮ Parameterized Algorithms and Kernels for Rainbow Matching ⋮ Disproof of a conjecture on the rainbow triangles in arc-colored digraphs ⋮ $(g,f)$-Chromatic spanning trees and forests ⋮ A NOTE ON RAINBOW MATCHINGS ⋮ Existences of rainbow matchings and rainbow matching covers ⋮ Note on rainbow triangles in edge-colored graphs ⋮ Rainbow \(C_4\)'s and directed \(C_4\)'s: the bipartite case study

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polychromatic Hamilton cycles
• On linear k-arboricity
• Rainbow \(H\)-factors
• An improved bound for the monochromatic cycle partition number
• On lengths of rainbow cycles
• Heterochromatic tree partition numbers for complete bipartite graphs
• Vertex partitions of \(r\)-edge-colored graphs
• Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Partitioning by monochromatic trees
• Maximum degree and fractional matchings in uniform hypergraphs
• Vertex coverings by monochromatic cycles and trees
• Multicolored forests in bipartite decompositions of graphs
• Latin squares. New developments in the theory and applications
• Transversals of latin squares and their generalizations
• Alternating Hamiltonian cycles
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• Partitioning complete bipartite graphs by monochromatic cycles
• Edge-colorings of complete graphs that avoid polychromatic trees
• The minimum labeling spanning trees
• Vertex partitions by connected monochromatic \(k\)-regular graphs
• Matchings and covers in hypergraphs
• Dense graphs without 3-regular subgraphs
• Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold
• Monochromatic infinite paths
• On the minimum monochromatic or multicolored subgraph partition problems
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph
• Long heterochromatic paths in edge-colored graphs
• Colorful isomorphic spanning trees in complete graphs
• On maximal paths and circuits of graphs
• Rainbow subgraphs in properly edge‐colored graphs
• Monochromatic Paths in Graphs
• Spanning trees with many or few colors in edge-colored graphs
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Edge colorings of complete graphs without tricolored triangles
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Local Anti-Ramsey Numbers of Graphs
• Partitioning complete multipartite graphs by monochromatic trees
• Vertex coverings by monochromatic paths and cycles
• On the existence of a rainbow 1‐factor in 1‐factorizations of K
• An anti-Ramsey Theorem on edge-cutsets
• Multicolored trees in complete graphs
• Multicolored trees in complete graphs
• Multicolored forests in complete bipartite graphs
• A generalization of the Gallai-Roy theorem

This page was built for publication: Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey