On a Vertex-Edge Marking Game on Graphs - Université de Bourgogne Accéder directement au contenu
Article Dans Une Revue Annals of Combinatorics Année : 2021

On a Vertex-Edge Marking Game on Graphs

Résumé

The study of a variation of the marking game, in which the first player marks vertices and the second player marks edges of an undirected graph was proposed by Bartnicki et al. (Electron J Combin 15:R72, 2008). In this game, the goal of the second player is to mark as many edges around an unmarked vertex as possible, while the first player wants just the opposite. In this paper, we prove various bounds for the corresponding graph invariant, the vertex-edge coloring number colve(G) of a graph G. In particular, every (finite or infinite) graph G whose edges can be oriented in such a way that the maximum out-degree is bounded by an integer d has colve(G)≤d+2. We investigate this invariant in (classes of) planar graphs, including some infinite lattices. We present a close connection between the vertex-edge coloring number of a graph G and the game coloring number of the subdivision graph S(G). In our main result, we bound the vertex-edge coloring number in complete graphs from below and from above, and while colve(Kn)≤⌈log2n⌉+2, the difference between the upper and the lower bound is roughly log2(log2n). The latter results are, in fact, true for any multigraph whose underlying graph is Kn.
Fichier principal
Vignette du fichier
On_a_vertex-edge_marking_ game_on_graphs_2020.pdf (301.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03150694 , version 1 (23-06-2021)

Identifiants

Citer

Boštjan Brešar, Nicolas Gastineau, Tanja Gologranc, Olivier Togni. On a Vertex-Edge Marking Game on Graphs. Annals of Combinatorics, 2021, 25, pp.179-194. ⟨10.1007/s00026-021-00524-9⟩. ⟨hal-03150694⟩
72 Consultations
98 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More