Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaker Breaker Games on an infinite board: Vertex Colouring
112
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We investigate games played between Maker and Breaker on an infinite complete graph whose vertices are coloured with colours from a given set, each colour appearing infinitely often. The players alternately claim edges, Makers aim being to claim all edges of a sufficiently colourful infinite complete subgraph and Breakers aim being to prevent this. We show that if there are only finitely many colours then Maker can obtain a complete subgraph in which all colours appear infinitely often, but that Breaker can prevent this if there are infinitely many colours. Even when there are infinitely many colours, we show that Maker can obtain a complete subgraph in which infinitely many of the colours each appear infinitely often.
rate research
Read More
By now, the Maker-Breaker connectivity game on a complete graph $K_n$ or on a random graph $Gsim G_{n,p}$ is well studied. Recently, London and Pluhar suggested a variant in which Maker always needs to choose her edges in such a way that her graph stays connected. By their results it follows that for this connected version of the game, the threshold bias on $K_n$ and the threshold probability on $Gsim G_{n,p}$ for winning the game drastically differ from the corresponding values for the usual Maker-Breaker version, assuming Makers bias to be $1$. However, they observed that the threshold biases of bo
We consider the Maker-Breaker positional game on the vertices of the $n$-dimensional hypercube ${0,1}^n$ with $k$-dimensional subcubes as winning sets. We describe a pairing strategy which allows Breaker to win when $k = n/4 +1$ in the case where $n$ is a power of 4. Our results also imply the general result that there is a Breakers win pairing strategy for any $n geq 3$ if $k = leftlfloorfrac{3}{7}nrightrfloor +1$.
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? We answer this question in the affirmative for triangle-free graphs.
Following a given ordering of the edges of a graph $G$, the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus involved is the chromatic index $chi(G)$, and the maximum is the so-called Grundy chromatic index. Here, we are interested in the restricted case where the ordering of the edges builds the graph in a connected fashion. Let $chi_c(G)$ be the minimum number of colours involved following such an ordering. We show that it is NP-hard to determine whether $chi_c(G)>chi(G)$. We prove that $chi(G)=chi_c(G)$ if $G$ is bipartite, and that $chi_c(G)leq 4$ if $G$ is subcubic.
An edge-coloured cycle is $rainbow$ if all edges of the cycle have distinct colours. For $kgeq 1$, let $mathcal{F}_{k}$ denote the family of all graphs with the property that any $k$ vertices lie on a cycle. For $Gin mathcal{F}_{k}$, a $k$-$rainbow$ $cycle$ $colouring$ of $G$ is an edge-colouring such that any $k$ vertices of $G$ lie on a rainbow cycle in $G$. The $k$-$rainbow$ $cycle$ $index$ of $G$, denoted by $crx_{k}(G)$, is the minimum number of colours needed in a $k$-rainbow cycle colouring of $G$. In this paper, we restrict our attention to the computational aspects of $k$-rainbow cycle colouring. First, we prove that the problem of deciding whether $crx_1=3$ can be solved in polynomial time, but that of deciding whether $crx_1 leq k$ is NP-Complete, where $kgeq 4$. Then we show that the problem of deciding whether $crx_2=3$ can be solved in polynomial time, but those of deciding whether $crx_2 leq 4$ or $5$ are NP-Complete. Furthermore, we also consider the cases of $crx_3=3$ and $crx_3 leq 4$. Finally, We prove that the problem of deciding whether a given edge-colouring (with an unbounded number of colours) of a graph is a $k$-rainbow cycle colouring, is NP-Complete for $k=1$, $2$ and $3$, respectively. Some open problems for further study are mentioned.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
