Back to Search
Start Over
On the game chromatic number of sparse random graphs
- Publication Year :
- 2012
- Publisher :
- arXiv, 2012.
-
Abstract
- Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of $G$ are colored. The game chromatic number \chi_g(G) is the minimum k for which the first player has a winning strategy. The paper \cite{BFS} began the analysis of the asymptotic behavior of this parameter for a random graph G_{n,p}. This paper provides some further analysis for graphs with constant average degree i.e. np=O(1) and for random regular graphs.<br />Comment: Correction
- Subjects :
- Random graph
High probability
Discrete mathematics
Computer Science::Computer Science and Game Theory
General Mathematics
010102 general mathematics
ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION
0102 computer and information sciences
01 natural sciences
Graph
Combinatorics
010201 computation theory & mathematics
FOS: Mathematics
Cubic graph
Mathematics - Combinatorics
19999 Mathematical Sciences not elsewhere classified
Chromatic scale
Combinatorics (math.CO)
0101 mathematics
Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....5544756ea1e11721a4879bf4b0e33d59
- Full Text :
- https://doi.org/10.48550/arxiv.1201.0046