The game coloring number of pseudo partial k-trees

DOI10.1016/S0012-365X(99)00237-XMaRDI QIDQ1974537zbMATH OpenOpenAlexFDO

Authors Xuding Zhu

Publication date 12 November 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00237-x

zbMATH Keywords

embeddinggame coloring numbergenuspartial \(k\)-trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35)

Review text

The author introduces the class of \((a,b)\)-pseudo partial \(k\)-trees, where the parameters \(a\) and \(b\) measure a graph's deviation from being a partial \(k\)-tree (the case \(a= b= 0\)). It is shown that the game coloring number of an \((a,b)\)-pseudo partial \(k\)-tree is at most \(3k+ 2a+ b+ 2\); for \(a= b= 0\), this greatly improves the bound of \textit{T. Dinski} and the author [Discrete Math. 196, No. 1-3, 109-115 (1999; Zbl 0928.05022)]. It is also shown that the game coloring number of an \((a,b)\)-pseudo partial \(k\)-tree is at most \(a+ b+8\); this leads to an upper bound of \(\lfloor(1/2)(3\sqrt{1+ 48g}+ 23\rfloor\) for the game coloring number of a graph imbeddable in the closed orientable 2-manifold of genus \(g\geq 1\).

Recommendations

• Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs
• Coloring games on squares of graphs
• Radius two trees specify χ‐bounded classes
• Marking games and the oriented game chromatic number of partial k-trees

Cited in

(53)

• Relaxed very asymmetric coloring games
• Game-perfect 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
• Circular game chromatic number of graphs
• Game colouring of the square of graphs
• A simple competitive graph coloring algorithm. II.
• The game coloring number of planar graphs with a specific girth
• Relaxed game chromatic number of trees and outerplanar graphs
• A simple competitive graph coloring algorithm. III
• Game-perfect digraphs
• The strong game colouring number of directed graphs
• The game Grundy number of graphs
• The game coloring number of planar graphs with a given girth
• Infinite chromatic games
• \textsf{PSPACE}-hardness of variants of the graph coloring game
• PSPACE-hardness of two graph coloring games
• On caterpillars of game chromatic number 4
• PSPACE-completeness of two graph coloring games
• Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs
• Refined activation strategy for the marking game
• Weak acyclic coloring and asymmetric coloring games
• Very asymmetric marking games
• On the hat guessing number of a planar graph class
• The connected greedy coloring game
• A note on the connected game coloring number
• Game chromatic index of \(k\)-degenerate graphs
• The game colouring number of powers of forests
• Efficient graph packing via game colouring
• Game coloring the Cartesian product of graphs
• Coloring games on squares of graphs
• Adapted game colouring of graphs
• The coloring game on planar graphs with large girth, by a result on sparse cactuses
• Game chromatic number of toroidal grids
• Game chromatic number of Cartesian product graphs
• Game chromatic number of toroidal grids
• Graph colorings with restricted bicolored subgraphs: II. The graph coloring game
• Decomposing planar graphs into graphs with degree restrictions
• Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs
• On the degree of trees with game chromatic number 4
• Decomposition of toroidal graphs without some subgraphs
• Decomposing graphs of nonnegative characteristic into subgraphs with degree restrictions
• Introduction to competitive graph coloring
• The specification of 2-trees
• A sufficient condition for nonnegative characteristic graphs to be (2, 1)-decomposable
• Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers
• The game chromatic number and the game colouring number of cactuses
• The relaxed game chromatic index of k-degenerate graphs
• The relaxed edge-coloring game and \(k\)-degenerate graphs
• Note on the game colouring number of powers of graphs
• Activation strategy for asymmetric marking games
• The 6-relaxed game chromatic number of outerplanar graphs

This page was built for publication: The game coloring number of pseudo partial \(k\)-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1974537)