Efficient Graph Packing via Game Colouring

DOI10.1017/S0963548309009973zbMath1197.05118OpenAlexW1989513471MaRDI QIDQ3552503

Henry A. Kierstead, Alexandr V. Kostochka

Publication date: 22 April 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548309009973

zbMATH Keywords

graph packinggame coloring

Mathematics Subject Classification ID

Games involving graphs (91A43) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

On caterpillars of game chromatic number 4, The independence coloring game on graphs, Chromatic numbers of exact distance 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, Maximum 0-1 timed matching on temporal graphs, Adapted game colouring of graphs, On the degree of trees with game chromatic number 4, Indicated coloring game on Cartesian products of graphs, Game chromatic number of generalized Petersen graphs and Jahangir graphs, Uniform orderings for generalized coloring numbers, Domination game on uniform hypergraphs, Indicated coloring of graphs, Circular game chromatic number of graphs, 2-coloring number revisited, Uniquely colorable graphs with equal chromatic and game chromatic numbers, On game chromatic vertex-critical graphs

Cites Work

• Edge disjoint placement of graphs
• The Ramsey number of a graph with bounded maximum degree
• Packings of graphs and applications to computational complexity
• A bound for the game chromatic number of graphs
• Marking games and the oriented game chromatic number of partial \(k\)-trees
• A simple competitive graph coloring algorithm
• Orderings on graphs and game coloring number
• Subgraphs of graphs. I
• The game coloring number of pseudo partial \(k\)-trees
• Graphs with linearly bounded Ramsey numbers
• An Ore-type analogue of the Sauer-Spencer theorem
• Grad and classes with bounded expansion. I: Decompositions
• Refined activation strategy for the marking game
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On Two Conjectures on Packing of Graphs