Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs
From MaRDI portal
Publication:5005187
DOI10.4230/LIPIcs.MFCS.2018.83OpenAlexW2889214486MaRDI QIDQ5005187
Juho Lauri, Pinar Heggernes, Erik Jan van Leeuwen, Davis Issac, Paloma T. Lima
Publication date: 4 August 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.83
Related Items (4)
Algorithms for the rainbow vertex coloring problem on graph classes ⋮ Rainbow vertex-connection number on a small-world Farey graph ⋮ WEIGHTED \(S^p\)-PSEUDO \(S\)-ASYMPTOTICALLY PERIODIC SOLUTIONS FOR SOME SYSTEMS OF NONLINEAR DELAY INTEGRAL EQUATIONS WITH SUPERLINEAR PERTURBATION ⋮ Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
Cites Work
- Unnamed Item
- Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
- Rainbow colouring of split graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Further hardness results on the rainbow vertex-connection number of graphs
- Rainbow connection in oriented graphs
- Hardness and algorithms for rainbow connection
- Complexity of rainbow vertex connectivity problems for restricted graph classes
- The complexity of determining the rainbow vertex-connection of a graph
- Further hardness results on rainbow and strong rainbow connectivity
- Bipartite permutation graphs
- Some simplified NP-complete graph problems
- On the complexity of rainbow coloring problems
- Rainbow connections of graphs: a survey
- Linear structure of bipartite permutation graphs and the longest path problem
- New Hardness Results in Rainbow Connectivity
- Rainbow Colouring of Split and Threshold Graphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Inapproximability of Rainbow Colouring
- Rainbow connection in graphs
- Graph Classes: A Survey
- On the Fine-Grained Complexity of Rainbow Coloring
- Fine-Grained Complexity of Rainbow Coloring and its Variants.
- The rainbow connection of a graph is (at most) reciprocal to its minimum degree
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- The strong rainbow vertex-connection of graphs
This page was built for publication: Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs