The harmonious coloring game

DOI10.1016/J.IPL.2025.106609MaRDI QIDQ6875951zbMATH OpenFDO

Authors Cláudia L. Sales, Thiago Marcilon, N. Martins, Nicolas Nisse, Rudini M. Sampaio

Publication date 13 January 2026

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2025.106609

zbMATH Keywords

game chromatic numberharmonious \(k\)-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Cites work

• \textsf{PSPACE}-hardness of variants of the graph coloring game
• A bound for the game chromatic number of graphs
• A new game chromatic number
• Deciding the on-line chromatic number of a graph with pre-coloring is PSPACE-complete
• Harmonious coloring on subclasses of colinear graphs
• Harmonious coloring: parameterized algorithms and upper bounds
• scientific article; zbMATH DE number 3710117 (Why is no real title available?)
• scientific article; zbMATH DE number 398953 (Why is no real title available?)
• scientific article; zbMATH DE number 3795986 (Why is no real title available?)
• New upper bounds on harmonious colorings
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On the harmonious chromatic number of a graph
• On the harmonious coloring of collections of graphs
• On the Harmonious Coloring of Graphs
• Online chromatic number is PSPACE-complete
• PSPACE-completeness of two graph coloring games
• Radius two trees specify χ‐bounded classes
• The complexity of harmonious colouring for trees
• The connected greedy coloring game
• The edge-distinguishing chromatic number of petal graphs, chorded cycles, and spider graphs
• The game chromatic number of random graphs
• The harmonious chromatic number of complete \(r\)-ary trees
• The harmonious coloring problem is NP-complete for interval and permutation graphs

This page was built for publication: The harmonious coloring game

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