Tropical dominating sets in vertex-coloured graphs

DOI10.1016/j.jda.2018.03.001zbMath1391.05193arXiv1503.01008OpenAlexW1561452800WikidataQ59072308 ScholiaQ59072308MaRDI QIDQ1748204

Csilla Bujtás, A. El Maftouhi, Zsolt Tuza, J.-A. Anglès d'Auriac, Marek Karpinski, Johan Thapper, Laurent Rosaz, Yannis Manoussakis, Leandro Montero, Narayanan Narayanan, Hakim El Maftouhi

Publication date: 9 May 2018

Published in: Journal of Discrete Algorithms, WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.01008

zbMATH Keywords

approximationrandom graphsdominating setvertex-coloured graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Tropical matchings in vertex-colored graphs ⋮ Enumeration of minimal tropical connected sets ⋮ Some rainbow problems in graphs have complexity equivalent to satisfiability problems ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Unnamed Item ⋮ Tropical paths in vertex-colored graphs ⋮ Maximum colorful independent sets in vertex-colored graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simultaneous domination in graphs
• Colorful paths in vertex coloring of graphs
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Simple proofs of results on paths representing all colors in proper vertex-colorings
• Approximation hardness of dominating set problems in bounded degree graphs
• Some APX-completeness results for cubic graphs
• Domination in graphs of minimum degree five
• Factor domination in graphs
• Domination in graphs with minimum degree two
• DOMINATION IN GRAPHS OF MINIMUM DEGREE FOUR
• Approximation algorithms for NP-complete problems on planar graphs
• Paths, Stars and the Number Three
• Paths in graphs
• Analytical approach to parallel repetition
• On the Concentration of the Domination Number of the Random Graph
• On the domination number of a random graph
• A generalization of the Gallai-Roy theorem