Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe game chromatic number of trees and forests
163
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree 3 and game chromatic number 4.
rate research
Read More
A new 2-parameter family of central structures in trees, called central forests, is introduced. Miniekas $m$-center problem and McMorriss and Reids central-$k$-tree can be seen as special cases of central forests in trees. A central forest is defined as a forest $F$ of $m$ subtrees of a tree $T$, where each subtree has $k$ nodes, which minimizes the maximum distance between nodes not in $F$ and those in $F$. An $O(n(m+k))$ algorithm to construct such a central forest in trees is presented, where $n$ is the number of nodes in the tree. The algorithm either returns with a central forest, or with the largest $k$ for which a central forest of $m$ subtrees is possible. Some of the elementary properties of central forests are also studied.
We determine the asymptotic behaviour of the chromatic number of exchangeable random graphs defined by step-regulated graphons. Furthermore, we show that the upper bound holds for a general graphon. We also extend these results to sparse random graphs obtained by percolations on graphons.
Resolving a problem raised by Norin, we show that for each $k in mathbb{N}$, there exists an $f(k) le 7k$ such that every graph $G$ with chromatic number at least $f(k)+1$ contains a subgraph $H$ with both connectivity and chromatic number at least $k$. This result is best-possible up to multiplicative constants, and sharpens earlier results of Alon-Kleitman-Thomassen-Saks-Seymour from 1987 showing that $f(k) = O(k^3)$, and of Chudnovsky-Penev-Scott-Trotignon from 2013 showing that $f(k) = O(k^2)$. Our methods are robust enough to handle list colouring as well: we also show that for each $k in mathbb{N}$, there exists an $f_ell(k) le 4k$ such that every graph $G$ with list chromatic number at least $f_ell(k)+1$ contains a subgraph $H$ with both connectivity and list chromatic number at least $k$. This result is again best-possible up to multiplicative constants; here, unlike with $f(cdot)$, even the existence of $f_ell(cdot)$ appears to have been previously unknown.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.
By a finite type-graph we mean a graph whose set of vertices is the set of all $k$-subsets of $[n]={1,2,ldots, n}$ for some integers $nge kge 1$, and in which two such sets are adjacent if and only if they realise a certain order type specified in advance. Examples of such graphs have been investigated in a great variety of contexts in the literature with particular attention being paid to their chromatic number. In recent joint work with Tomasz {L}uczak, two of the authors embarked on a systematic study of the chromatic numbers of such type-graphs, formulated a general conjecture determining this number up to a multiplicative factor, and proved various results of this kind. In this article we fully prove this conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
