Showing 2004Show all
2 papers · 1 filter
cs.CC2004
On the Computational Complexity of the Forcing Chromatic Number
Frank Harary, Wolfgang Slany, Oleg Verbitsky
We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is -chromatic if it is colorable in colors and any coloring of it uses at lea…
math.CO2004
On the Lengths of Symmetry Breaking-Preserving Games on Graphs
Frank Harary, Wolfgang Slany, Oleg Verbitsky
Given a graph , we consider a game where two players, and , alternatingly color edges of in red and in blue respectively. Let be the maximum number of moves in…