Maximum colored trees in edge-colored graphs

DOI10.1016/J.EJC.2018.02.027MaRDI QIDQ2311375zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 10 July 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2018.02.027

zbMATH Keywords

properly edge-colored spanning trees

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Spanning trees with many or few colors in edge-colored graphs
• Properly colored spanning trees in edge-colored graphs
• Maximum properly colored trees in edge-colored graphs
• Sufficient conditions for the existence of spanning colored trees in edge-colored graphs
• Paths and trails in edge-colored graphs

Cites work

• A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph
• A note on alternating cycles in edge-coloured graphs
• Alternating cycles in edge-partitioned graphs
• Alternating paths in edge-colored complete graphs
• An O(EV\log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Multicolored forests in bipartite decompositions of graphs
• Multicolored forests in complete bipartite graphs
• Multicolored trees in complete graphs
• Paths and trails in edge-colored graphs

Cited in

(15)

• On an extremal problem for colored trees
• Maximum properly colored trees in edge-colored graphs
• Properly colored spanning trees in edge-colored graphs
• On trees with a maximum proper partial 0-1 coloring containing a maximum matching
• Extremal trees with respect to number of (A, B, 2 C)-edge colourings
• Spanning trees with many or few colors in edge-colored graphs
• Multicolored trees in random graphs
• Sufficient conditions for the existence of spanning colored trees in edge-colored graphs
• Color-avoiding connected spanning subgraphs with minimum number of edges
• Colored constrained spanning tree on directed graphs
• Parallel connectivity in edge-colored complete graphs: complexity results
• Approximating maximum-size properly colored forests
• Approximating maximum-size properly colored forests
• Properly colored spanning trees via subdivision of a given tree in monochromatic triangle-free edge-colored complete graphs
• The parameterized complexity of the properly colored spanning tree problem

This page was built for publication: Maximum colored trees in edge-colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2311375)