Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOnline coloring a token graph
70
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study a combinatorial coloring game between two players, Spoiler and Algorithm, who alternate turns. First, Spoiler places a new token at a vertex in $G$, and Algorithm responds by assigning a color to the new token. Algorithm must ensure that tokens on the same or adjacent vertices receive distinct colors. Spoiler must ensure that the token graph (in which two tokens are adjacent if and only if their distance in $G$ is at most $1$) has chromatic number at most $w$. Algorithm wants to minimize the number of colors used, and Spoiler wants to force as many colors as possible. Let $f(w,G)$ be the minimum number of colors needed in an optimal Algorithm strategy. A graph $G$ is online-perfect if $f(w,G) = w$. We give a forbidden induced subgraph characterization of the class of online-perfect graphs. When $G$ is not online-perfect, determining $f(w,G)$ seems challenging; we establish $f(w,G)$ asymptotically for some (but not all) of the minimal graphs that are not online-perfect. The game is motivated by a natural online coloring problem on the real line which remains open.
rate research
Read More
We prove that every partial function with finite domain and range can be effectively simulated through sequential colorings of graphs. Namely, we show that given a finite set $S={0,1,ldots,m-1}$ and a number $n geq max{m,3}$, any partial function $varphi:S^{^p} to S^{^q}$ (i.e. it may not be defined on some elements of its domain $S^{^p}$) can be effectively (i.e. in polynomial time) transformed to a simple graph $matr{G}_{_{varphi,n}}$ along with three sets of specified vertices $$X = {x_{_{0}},x_{_{1}},ldots,x_{_{p-1}}}, Y = {y_{_{0}},y_{_{1}},ldots,y_{_{q-1}}}, R = {Kv{0},Kv{1},ldots,Kv{n-1}},$$ such that any assignment $sigma_{_{0}}: X cup R to {0,1,ldots,n-1} $ with $sigma_{_{0}}(Kv{i})=i$ for all $0 leq i < n$, is {it uniquely} and {it effectively} extendable to a proper $n$-coloring $sigma$ of $matr{G}_{_{varphi,n}}$ for which we have $$varphi(sigma(x_{_{0}}),sigma(x_{_{1}}),ldots,sigma(x_{_{p-1}}))=(sigma(y_{_{0}}),sigma(y_{_{1}}),ldots,sigma(y_{_{q-1}})),$$ unless $(sigma(x_{_{0}}),sigma(x_{_{1}}),ldots,sigma(x_{_{p-1}}))$ is not in the domain of $varphi$ (in which case $sigma_{_{0}}$ has no extension to a proper $n$-coloring of $matr{G}_{_{varphi,n}}$).
Hadwiger Conjecture has been an open problem for over a half century1,6, which says that there is at most a complete graph Kt but no Kt+1 for every t-colorable graph. A few cases of Hadwiger Conjecture, such as 1, 2, 3, 4, 5, 6-colorable graphs have been completely proved to convince all1-5, but the proofs are tremendously difficult for over the 5-colorable graph6,7. Although the development of graph theory inspires scientists to understand graph coloring deeply, it is still an open problem for over 7-colorable graphs6,7. Therefore, we put forward a brand new chromatic graph configuration and show how to describe the graph coloring issues in chromatic space. Based on this idea, we define a chromatic plane and configure the chromatic coordinates in Euler space. Also, we find a method to prove Hadwiger Conjecture for every 8-coloring graph feasible.
We introduce the notion of a properly ordered coloring (POC) of a weighted graph, that generalizes the notion of vertex coloring of a graph. Under a POC, if $xy$ is an edge, then the larger weighted vertex receives a larger color; in the case of equal weights of $x$ and $y$, their colors must be different. In this paper, we shall initiate the study of this special coloring in graphs. For a graph $G$, we introduce the function $f(G)$ which gives the maximum number of colors required by a POC over all weightings of $G$. We show that $f(G)=ell(G)$, where $ell(G)$ is the number of vertices of a longest path in $G$. Another function we introduce is $chi_{POC}(G;t)$ giving the minimum number of colors required over all weightings of $G$ using $t$ distinct weights. We show that the ratio of $chi_{POC}(G;t)-1$ to $chi(G)-1$ can be bounded by $t$ for any graph $G$; in fact, the result is shown by determining $chi_{POC}(G;t)$ when $G$ is a complete multipartite graph. We also determine the minimum number of colors to give a POC on a vertex-weighted graph in terms of the number of vertices of a longest directed path in an orientation of the underlying graph. This extends the so called Gallai-Hasse-Roy-Vitaver theorem, a classical result concerning the relationship between the chromatic number of a graph $G$ and the number of vertices of a longest directed path in an orientation of $G$.
Let G be a simple graph. A coloring of vertices of G is called (i) a 2-proper coloring if vertices at distance 2 receive distinct colors; (ii) an injective coloring if vertices possessing a common neighbor receive distinct colors; (iii) a square coloring if vertices at distance at most 2 receive distinct colors. In this paper, we study inequalities of Nordhaus-Guddam type for the 2-proper chromatic number, the injective chromatic number, and the square chromatic number.
In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(mathcal{C} d N^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(mathcal{C} d)$-coloring with $O(d N^{1/d})$ recolorings per update. The two converge when $d = log N$, maintaining an $O(mathcal{C} log N)$-coloring with $O(log N)$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $Omega(N^frac{2}{c(c-1)})$ vertices per update, for any constant $c geq 2$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
