Rainbow graph splitting

DOI10.1016/J.TCS.2011.06.004MaRDI QIDQ719272zbMATH OpenOpenAlexFDO

Authors Angelo Monti, Blerina Sinaimeri

Publication date 10 October 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.06.004

zbMATH Keywords

algorithmscomplexityedge-coloringvertex partition

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Rainbow colouring of split graphs
• Rainbow Colouring of Split and Threshold Graphs
• Covering Graphs by Colored Stable Sets
• Complexity results for two kinds of colored disconnections of graphs
• Generalized rainbow connectivity of graphs

Cites work

• A finite basis characterization of alpha-split colorings
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A simplified NP-complete satisfiability problem
• Adapted List Coloring of Graphs and Hypergraphs
• An asymptotically tight bound on the adaptable chromatic number
• An efficiently solvable graph partition problem to which many problems are reducible
• Complexity of graph partition problems
• Full Constraint Satisfaction Problems
• Graph colourings and partitions
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Minimal colorings for properly colored subgraphs
• On the adaptable chromatic number of graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the minimum monochromatic or multicolored subgraph partition problems
• Partitions of graphs into one or two independent sets and cliques
• Two algorithms for general list matrix partitions

Cited in

(7)

• Colorful edge decomposition of graphs: some polynomial cases
• Rainbow Colouring of Split and Threshold Graphs
• Almost all asters are splittable
• On splittable colorings of graphs and hypergraphs
• Covering Graphs by Colored Stable Sets
• Rainbow colouring of split graphs
• Rainbow tetrahedra in Cayley graphs

This page was built for publication: Rainbow graph splitting

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