Rainbow graph splitting
From MaRDI portal
Publication:719272
DOI10.1016/j.tcs.2011.06.004zbMath1225.68137MaRDI QIDQ719272
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15: Coloring of graphs and hypergraphs
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simplified NP-complete satisfiability problem
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A finite basis characterization of alpha-split colorings
- Partitions of graphs into one or two independent sets and cliques
- An efficiently solvable graph partition problem to which many problems are reducible
- On the adaptable chromatic number of graphs
- On the minimum monochromatic or multicolored subgraph partition problems
- Minimal colorings for properly colored subgraphs
- Complexity of graph partition problems
- Adapted List Coloring of Graphs and Hypergraphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- An asymptotically tight bound on the adaptable chromatic number
- Full Constraint Satisfaction Problems
- Graph colourings and partitions