Oriented coloring of 2-dimensional grids

Zorientowane kolorownie skierowanego grafu −→G to homomorfizm grafu −→G w skierowany graf −→H, który nie ma p¸etli ani łuków w przeciwnych kierunkach. Zorientowana liczba chromatyczna −→χ ( −→G) skierowanego grafu −→G, to najmniejsza liczba wierzchołków w grafie −→H, dla którego istnieje homomorfizm z grafu −→G w graf −→H. Zorientowana liczba chromatyczna grafu nieskierowanego to maksymalna zorientowana liczba chromatyczna po wszystkich orientacjach grafu G. Tematem tej rozprawy jest zorientowana liczba chromatyczna czterech klas grafów: 2-wymiarowych krat, cylindrycznych krat, toroidalnych krat oraz silnych krat. 2-wymiarowa krata G(m, n) to iloczyn kartezjański PmPn dwóch ścieżek o m i n wierzchołkach, cylindryczna krata Cyl(m, n) = CmPn to iloczyn kartezjański cyklu Cm i ścieżki Pn, natomiast iloczyn kartezjański dwóch cykli to krata toroidalna T(m, n) = CmCn. Siln¸a krat¸a G(m, n) = Pm Pn nazywamy silny iloczyn dwóch ścieżek o m i n wierzchołkach. Ściśle powi¸azane z kolorowaniem zorientowanym jest kolorowanie oznakowane. Oznakowany graf (ang. signed graph) to para (G, σ), gdzie G = (V (G), E(G)) jest nieskierowanym grafem, a σ : E(G) → {+, −} to funkcja przyporz¸adkowuj¸aca każdej kraw¸edzi znak ”+” lub ”−”. Dwa oznakowane grafy s¸a równoważne, jeśli jeden z nich może być zamieniony w drugi za pomoc¸a ci¸agu operacji zmiany znaków. Pojedyncza operacja zmiany znaków, dla wybranego wierzchołka v ∈ V (G), zamienia znaki wszytkich kraw¸edzi incydentnych z v. Poprzez [G, σ] b¸edziemy oznaczać klas¸e równoważności grafu oznakowanego (G, σ). Każdy element klasy [G, σ] nazywamy reprezentantem tej klasy. Kolorowanie grafów oznakowanych definiujemy poprzez homomorfizm. Graf oznakowany [G, σ] jest kolorowalny za pomoc¸a (G2, σ2), jeżeli istnieje reprezentant (G, σ1) klasy [G, σ] i odwzorowanie φ z V (G) w V (G2) zachowyj¸ace znaki kraw¸edzi. Oznakowana liczba chromatyczna oznakowanego grafu [G, σ] to najmniejsza liczba wierzchołków grafu koloruj¸acego graf [G, σ]. Oznakowana liczba chromatyczna χs(G) grafu G to maksymalna liczba spośród wszystkich oznakowanych liczb chromatycznych wszystkich oznakowanych grafów powstałych na bazie G. v Główne wyniki rozprawy s¸a nast¸epuj¸ace: 1. Ustalamy now¸a doln¸a granic¸e osiem dla zorientowanej liczby chromatycznej krat, przedstawiaj¸ac orientacj¸e kraty, która wymaga ośmiu kolorów do zorientowanego kolorowania. Daje to również now¸a doln¸a granic¸e osiem dla rodziny wszystkich cylindrycznych krat oraz dla rodziny wszystkich toroidalnych krat. (Rozdział 3.) 2. Przedstawiamy skierowany graf z dziesi¸ecioma wierzchołkami, nazwany −→H10, taki, że dowolna orientacja kraty z ośmioma wierszami posiada homomrfizm w −→H10. Otrzymaliśmy w ten sposób nowe górne ograniczenie zorientowanej liczby chromatycznej dla rodzin wszystkich krat z sześcioma, siedmioma oraz ośmioma wierszami. (Rozdział 4.) 3. Pokazujemy, że dowolna orientacja toroidalnej kraty jest kolorowalna za pomoc¸a dwudziestu siedmiu kolorów. (Rozdział 6.) 4. Pokazujemy, że dowolna orientacja cylindrycznej kraty o obwodzie cyklu co najwyżej siedem może być pokolorowana przy pomocy −→H10. (Rozdział 6.) 5. Ustanawiamy now¸a górn¸a i doln¸a granic¸e zorientowanej liczby chromatycznej rodziny wszystkich silnych krat. Pokazujemy, że istnieje orientacja silnej kraty G(2, 398), która nie może być pokolorowana za pomoc¸a 10 kolorów. Wyznaczamy w ten sposób nowe dolne ograniczenie zorientowanej liczby chromatycznej wszystkich silnych krat. Ponadto, pokazujemy, że dowolna orientacja dowolnej silnej kraty może być pokolorowana za pomoc¸a osiemdziesi¸eciu ośmiu kolorów. (Rozdział 7.) 6. Pokazujemy, że dowolna oznakowana krata z co najwyżej siedmioma wierszami może być pokolorowana za pomoc¸a pi¸eciu kolorów. (Rozdział 8.) 7. Pokazujemy, że dolna granica oznakowanej liczby chromatycznej rodziny wszystkich krat jest pi¸eć. (Rozdział 8.) Wyniki przedstawiowe w dysertacji zostały opublikowane w pracach ([11–13]) lub s¸a przyj¸ete do publikacji w ([35]).

An oriented coloring of an oriented graph −→G is a homomorphism from −→G to an oriented graph −→H such that −→H has neither loops nor arcs in opposite directions. The oriented chromatic number −→χ ( −→G) of an oriented graph −→G is the smallest number of vertices of −→H for which there exists a homomorphism from −→G to −→H. The oriented chromatic number of an undirected graph is the maximal chromatic number over all possible orientations of G. In this thesis, we consider the oriented chromatic number of four families of graphs, namely: 2-dimensional grids, cylindrical grids, toroidal grids and strong-grids. A 2- dimensional grid G(m, n) is the Cartesian product PmPn of two paths on m and n vertices, the Cartesian product of a cycle Cm and a path Pn is called a cylindrical grid Cyl(m, n) = CmPn, whereas the Cartesian products of two cycles is called a toroidal grid T(m, n) = CmCn. A strong-grid G(m, n) is the strong product Pm Pn of two paths on m and n vertices. Closely related to oriented coloring is signed coloring. A signed graph is a pair (G, σ), where G = (V (G), E(G)) is an undirected graph and σ : E(G) → {+, −} is a function which marks each edge with ”+” or ”−”. Two signed graphs are equivalent if one of them can be changed to the other by a sequence of resigning operations. The single resigning operation chooses a vertex v ∈ V (G) and flips the signs of all edges incident to v. By [G, σ] we shall denote the equivalence class of the signed graph (G, σ). Each element of class [G, σ] is called a presentation. The coloring of signed graphs is defined through homomorphism. The signed graph [G, σ] is colored by the signed graph (G2, σ2), if there exists a presentation (G, σ1) of [G, σ] and a vertex-mapping φ from G to G2 which preserves signs of the edges. The signed chromatic number of the signed graph [G, σ], denoted by χs([G, σ]), is the size of the smallest graph which colors [G, σ]. The signed chromatic number χs(G) of the undirected graph G is the maximum of the signed chromatic numbers over all signed graphs with underlining graph G. The main results of the thesis are listed below: 1. We establish the new lower bound of eight for oriented chromatic number of the family of all grids by showing that there exists an orientation of a grid that cannot be colored by seven colors. This also gives the new lower bound of eight for the family of all cylindrical grids and for the family of all toroidal grids. (Chapter 3.) 2. We present an oriented graph with ten vertices, namely, −→H10, which colors all orientations of all grids with eight rows. This gives the new upper bound of ten for the oriented chromatic number for the families of all grids with six, seven and eight rows. (Chapter 4.) 3. We show that every toroidal grid can be colored with twenty seven colors. (Chapter 6.) 4. We show that any orientation of any cylindrical grid with circuit at most seven can be colored by the graph −→H10. (Chapter 6.) 5. We give new lower and upper bounds for the oriented chromatic number of stronggrids. We show that there exists an orientation of a strong-grid G(2, 398) that cannot be colored with ten colors. This gives the new lower bound of eleven for the oriented chromatic number of the family of all strong-grids. Furthermore, we show that any orientation of any strong-grid can be colored with eighty eight colors. (Chapter 7.) 6. We show that any signed grid with at most seven rows can be colored with five colors. (Chapter 8.) 7. We show that the lower bound for the signed chromatic number of the family of all grids is five. (Chapter 8.) The main results of the dissertation are published in ([11–13]) or are accepted for publication ([35]).