Radius two trees specify χ‐bounded classes

DOI10.1002/jgt.3190180203zbMath0809.05044OpenAlexW2094108224MaRDI QIDQ4309985

Henry A. Kierstead, William T. jun. Trotter

Publication date: 20 March 1995

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190180203

zbMATH Keywords

planar graphslower boundsgamegame chromatic numberouterplanar graphwinning strategyplayers

Mathematics Subject Classification ID

Games involving graphs (91A43) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Related Items (70)

Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers ⋮ A simple competitive graph coloring algorithm. III ⋮ PSPACE-hardness of two graph coloring games ⋮ Note on the game chromatic index of trees ⋮ Chromatic numbers of exact distance graphs ⋮ Computer Science Unplugged and Related Projects in Math and Computer Science Popularization ⋮ Asymmetric coloring games on incomparability graphs ⋮ Bounds on the game transversal number in hypergraphs ⋮ Domination Game: A proof of the $3/5$-Conjecture for Graphs with Minimum Degree at Least Two ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices ⋮ On coloring numbers of graph powers ⋮ Generalised game colouring of graphs ⋮ On two problems in graph Ramsey theory ⋮ The relaxed game chromatic index of \(k\)-degenerate graphs ⋮ Unnamed Item ⋮ PSPACE-completeness of two graph coloring games ⋮ Maximum planar subgraphs in dense graphs ⋮ The relaxed edge-coloring game and \(k\)-degenerate graphs ⋮ A connected version of the graph coloring game ⋮ Adapted game colouring of graphs ⋮ A note on the Gyárfás-Sumner conjecture ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs ⋮ The strong game colouring number of directed graphs ⋮ On monotonicity in maker-breaker graph colouring games ⋮ Note on the game colouring number of powers of graphs ⋮ The connected greedy coloring game ⋮ The game chromatic index of wheels ⋮ The game Grundy number of graphs ⋮ Unnamed Item ⋮ The game \(L(d,1)\)-labeling problem of graphs ⋮ A simple competitive graph coloring algorithm. II. ⋮ On forbidden subdivision characterizations of graph classes ⋮ Uniform orderings for generalized coloring numbers ⋮ Game chromatic number of toroidal grids ⋮ Refined activation strategy for the marking game ⋮ The game Grundy indices of graphs ⋮ On the weak 2-coloring number of planar graphs ⋮ Planar graphs have two-coloring number at most 8 ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Game chromatic number of Cartesian product graphs ⋮ Game chromatic number of toroidal grids ⋮ A new upper bound on the game chromatic index of graphs ⋮ The incidence game chromatic number of paths and subgraphs of wheels ⋮ Ramsey-goodness -- and otherwise ⋮ Weak acyclic coloring and asymmetric coloring games ⋮ Rank-width and tree-width of \(H\)-minor-free graphs ⋮ The incidence game chromatic number of \((a,d)\)-decomposable graphs ⋮ The difference between game chromatic number and chromatic number of graphs ⋮ Game coloring the Cartesian product of graphs ⋮ The 6-relaxed game chromatic number of outerplanar graphs ⋮ Lightness of digraphs in surfaces and directed game chromatic number ⋮ Colouring games on outerplanar graphs and trees ⋮ Activation strategy for relaxed asymmetric coloring games ⋮ Infinite chromatic games ⋮ A simple competitive graph coloring algorithm ⋮ Relaxed game chromatic number of trees and outerplanar graphs ⋮ Fraternal augmentations, arrangeability and linear Ramsey numbers ⋮ \textsf{PSPACE}-hardness of variants of the graph coloring game ⋮ Circular game chromatic number of graphs ⋮ Game colouring of the square of graphs ⋮ Generalization of transitive fraternal augmentations for directed graphs and its applications ⋮ Colouring graphs with bounded generalized colouring number ⋮ A bound for the game chromatic number of graphs ⋮ 2-coloring number revisited ⋮ Game chromatic number of strong product graphs ⋮ The game coloring number of planar graphs ⋮ Approximation algorithms for routing and call scheduling in all-optical chains and rings. ⋮ Uniquely colorable graphs with equal chromatic and game chromatic numbers

Cites Work

• Unnamed Item
• Induced subtrees in graphs of large chromatic number
• A Ramsey-type theorem for traceable graphs
• On-line and first fit colorings of graphs
• On chromatic number of graphs and set-systems

This page was built for publication: Radius two trees specify χ‐bounded classes