Tropical dominating sets in vertex-coloured graphs

DOI10.1016/j.jda.2018.03.001zbMath1391.05193arXiv1503.01008WikidataQ59072308 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

approximation; random graphs; dominating set; vertex-coloured graph

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Unnamed Item, Tropical paths in vertex-colored graphs, Enumeration of minimal tropical connected sets, Maximum colorful independent sets in vertex-colored graphs, Efficient enumeration of dominating sets for sparse graphs, Tropical matchings 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