2-Edge-Colored Chromatic Number of Grids is at Most 9
2-Edge-Colored Chromatic Number of Grids is at Most 9
Abstract A 2-edge-colored graph is a pair $$(G, \sigma )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>,</mml:mo><mml:mi>σ</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> where G is a graph, and $$\sigma :E(G)\rightarrow \{\text {'}+\text {'},\text {'}-\text {'}\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>σ</mml:mi><mml:mo>:</mml:mo><mml:mi>E</mml:mi><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo><mml:mo>→</mml:mo><mml:mo>{</mml:mo><mml:mtext>'</mml:mtext><mml:mo>+</mml:mo><mml:mtext>'</mml:mtext><mml:mo>,</mml:mo><mml:mtext>'</mml:mtext><mml:mo>-</mml:mo><mml:mtext>'</mml:mtext><mml:mo>}</mml:mo></mml:mrow></mml:math> is a function which marks all edges with signs. A 2-edge-colored coloring of the 2-edge-colored graph $$(G, \sigma )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>,</mml:mo><mml:mi>σ</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> is a …