The lower and upper independent, domination and irredundant numbers of the graph G = (V, E) are denoted by i ( G) , f3 ( G), 'Y ( G), r ( G), ir ( G) and IR ( G) respectively. These six numbers are called the domination parameters. For each of these parameters n:, we define six types of criticality. The graph G is n:-critical (n:+ -critical) if the removal of any vertex of G causes n: (G) to decrease (increase), G is n:-edge-critical (n:+-edge-critical) if the addition of any missing edge causes n: (G) to decrease (increase), and G is Ir-ER-critical (n:- -ER-critical) if the removal of any edge causes n: (G) to increase (decrease). For all the above-mentioned parameters n: there exist graphs which are n:-critical, n:-edge-critical and n:-ER-critical. However, there do not exist any n:+-critical graphs for n: E {ir,"f,i,/3,IR}, no n:+-edge-critical graphs for n: E {ir,"f,i,/3} and non:--ER-critical graphs for: E {'Y,/3,r,IR}. Graphs which are "I-critical, i-critical, "I-edge-critical and i-edge-critical are well studied in the literature. In this thesis we explore the remaining types of criticality. We commence with the determination of the domination parameters of some wellknown classes of graphs. Each class of graphs we consider will turn out to contain a subclass consisting of graphs that are critical according to one or more of the definitions above. We present characterisations of "I-critical, i-critical, "I-edge-critical and i-edge-critical graphs, as well as ofn:-ER-critical graphs for n: E {/3,r,IR}. These characterisations are useful in deciding which graphs in a specific class are critical. Our main results concern n:-critical and n:-edge-critical graphs for n: E {/3, r, IR}. We show that the only /3-critical graphs are the edgeless graphs and that a graph is IRcritical if and only if it is r-critical, and proceed to investigate the r-critical graphs which are not /3-critical. We characterise /3-edge-critical and r-edge-critical graphs and show that the classes of IR-edge-critical and r-edge-critical graphs coincide. We also exhibit classes of r+ -critical, r+ -edge-critical and i- -ER-critical graphs. / Mathematical Sciences / D. Phil. (Mathematics)

The lower and upper independent, domination and irredundant numbers of the graph G = (V, E) are denoted by i ( G) , f3 ( G), 'Y ( G), r ( G), ir ( G) and IR ( G) respectively. These six numbers are called the domination parameters. For each of these parameters n:, we define six types of criticality. The graph G is n:-critical (n:+ -critical) if the removal of any vertex of G causes n: (G) to decrease (increase), G is n:-edge-critical (n:+-edge-critical) if the addition of any missing edge causes n: (G) to decrease (increase), and G is Ir-ER-critical (n:- -ER-critical) if the removal of any edge causes n: (G) to increase (decrease). For all the above-mentioned parameters n: there exist graphs which are n:-critical, n:-edge-critical and n:-ER-critical. However, there do not exist any n:+-critical graphs for n: E {ir,"f,i,/3,IR}, no n:+-edge-critical graphs for n: E {ir,"f,i,/3} and non:--ER-critical graphs for: E {'Y,/3,r,IR}. Graphs which are "I-critical, i-critical, "I-edge-critical and i-edge-critical are well studied in the literature. In this thesis we explore the remaining types of criticality. We commence with the determination of the domination parameters of some wellknown classes of graphs. Each class of graphs we consider will turn out to contain a subclass consisting of graphs that are critical according to one or more of the definitions above. We present characterisations of "I-critical, i-critical, "I-edge-critical and i-edge-critical graphs, as well as ofn:-ER-critical graphs for n: E {/3,r,IR}. These characterisations are useful in deciding which graphs in a specific class are critical. Our main results concern n:-critical and n:-edge-critical graphs for n: E {/3, r, IR}. We show that the only /3-critical graphs are the edgeless graphs and that a graph is IRcritical if and only if it is r-critical, and proceed to investigate the r-critical graphs which are not /3-critical. We characterise /3-edge-critical and r-edge-critical graphs and show that the classes of IR-edge-critical and r-edge-critical graphs coincide. We also exhibit classes of r+ -critical, r+ -edge-critical and i- -ER-critical graphs. / Mathematical Sciences / D. Phil. (Mathematics)

Let G and H be graphs. We say G is H-critical, if every proper subgraph of G except G itself is homomorphic to H. This generalizes the widely known concept of k-color-critical graphs, as they are the case H = Kk - 1. In 1963 [T. Gallai, Kritiche Graphen, I., Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 373-395], Gallai proved that the vertices of degree k in a Kk-critical graph induce a subgraph whose blocks are either odd cycles or complete graphs. We generalize Gallai's Theorem for every H-critical graph, where H = Kk - 2 + H′, (the join of a complete graph Kk - 2 with any graph H′). This answers one of the two unknown cases of a problem given in [J. Nešetřil, Y. Nigussie, Finite dualities and map-critical graphs on a fixed surface. (Submitted to Journal of Combin. Theory, Series B)]. We also propose an open question, which may be a characterization of all graphs for which Gallai's Theorem holds.

Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n - 1, G is said to be k-extendable if for every matching M of size k in G there is a perfect matching in G containing all the edges of M. A k-extendable graph G is said to be k-critical (k-minimal) if G+uv (G-uv) is not k-extendable for every non-adjacent (adjacent) pair of vertices u and v of G. The problem that arises is that of characterizing k-extendable, k-critical and k-minimal graphs.In Chapter 2, we establish that δ(G) ≥ 1/2(n + k) is a sufficient condition for a bipartite graph G on 2n vertices to be k-extendable. For a graph G on 2n vertices with δ(G) ≥ n + k 1, n - k even and n/2 ≤ k ≤ n - 2, we prove that a necessary and sufficient condition for G to be k-extendable is that its independence number is at most n - k. We also establish that a k-extendable graph G of order 2n has k + 1 ≤ δ(G) n or δ(G) ≥ 2k + 1, 1 ≤ k ≤ n - 1. Further, we establish the existence of a k-extendable graph G on 2n vertices with δ(G) = j for each integer j Є [k + 1, n] u [2k + 1, 2n 1]. For k = n - 1 and n - 2, we completely characterize k-extendable graphs on 2n vertices. We conclude Chapter 2 with a variation of the concept of extendability to odd order graphs.In Chapter 3, we establish a number of properties of k-critical graphs. These results include sufficient conditions for k-extendable graphs to be k-critical. More specifically, we prove that for a k-extendable graph G ≠ K2n on 2n vertices, 2 ≤ k ≤ n - 1, if for every pair of non-adjacent vertices u and v of G there exists a dependent set S ( a subset S of V (G) is dependent if the induced subgraph G[S] has at least one edge) of G-u-v such that o(G-(S u {u,v})) = S, then G is k-critical. Moreover, for k = 2 this sufficient condition is also a necessary condition for non-bipartite graphs. We also establish a ++ / necessary condition, in terms of the minimum degree, for k-critical graphs.We conclude Chapter 3 by completely characterizing k-critical graphs on 2n vertices for k = 1, n - 1 and n - 2.Chapter 4 contains results on k-minimal graphs. These results include necessary and sufficient conditions for k-extendable graphs to be k-minimal. More specifically, we prove that for a k-extendable graph G on 2n vertices, 1 ≤ k ≤ n - 1, the following are equivalent:G is minimalfor every edge e = uv of G there exists a matching M of size k in G-e such that V(M) n {u,v} = ø and for every perfect matching F in G containing M, e Є F.for every edge e = uv of G there exists a vertex set S of G-u-v such that: M(S) ≥ k; o(G-e-S) = S - 2k + 2; and u and v belong to different odd components of G-e-S, where M(S) denotes a maximum matching in G[S].We also establish a necessary condition, in terms of minimum degree, for k-minimal and k-minimal bipartite graphs. In fact, we prove that a k-minimal graph G ≠ K2n on 2n vertices, 1 ≤ k ≤ n - 1, has minimum degree at most n + k - 1. For a k-minimal bipartite graph G ≠ Kn,n , 1 ≤ k ≤ n - 3, we show that δ(G) < ½(n + k).Chapter 1 provides the notation, terminology, general concepts and the problems concerning extendability graphs and (k,t)-critical graphs.

Let K be a class of graphs. A pair (F,U) is a finite duality in K if U∈K, F is a finite set of graphs, and for any graph G in K we have G≤U if and only if F≤≰G for all F∈F, where "≤" is the homomorphism order. We also say U is a dual graph in K. We prove that the class of planar graphs has no finite dualities except for two trivial cases. We also prove that the class of toroidal graphs has no 5-colorable dual graphs except for two trivial cases. In a sharp contrast, for a higher genus orientable surface S we show that Thomassen's result (Thomassen, 1997 [17]) implies that the class, G(S), of all graphs embeddable in S has a number of finite dualities. Equivalently, our first result shows that for every planar core graph H except K1 and K4, there are infinitely many minimal planar obstructions for H-coloring (Hell and Nešetřil, 1990 [4]), whereas our later result gives a converse of Thomassen's theorem (Thomassen, 1997 [17]) for 5-colorable graphs on the torus.

For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent domination number i (G)) of G is the minimum cardinality amongst its dominating sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1- critical, if the domination number k decreases whenever an edge is added. Further, G is hamiltonian if it has a cycle that passes through each of its vertices. This dissertation assimilates research generated by two conjectures: Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian. Conjecture 2. If G is k-1-critical, then I ( G) = i ( G). The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture 2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)

For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent domination number i (G)) of G is the minimum cardinality amongst its dominating sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1- critical, if the domination number k decreases whenever an edge is added. Further, G is hamiltonian if it has a cycle that passes through each of its vertices. This dissertation assimilates research generated by two conjectures: Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian. Conjecture 2. If G is k-1-critical, then I ( G) = i ( G). The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture 2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)

Vizing conjectured in 1963 that the domination number of the Cartesian product of two graphs is at least the product of their domination numbers; this remains one of the biggest open problems in the study of domination in graphs. Several partial results have been proven, but the conjecture has yet to be proven in general. The purpose of this thesis was to study Vizing's conjecture, related results, and open problems related to the conjecture. We give a survey of classes of graphs that are known to satisfy the conjecture, and of Vizing-like inequalities and conjectures for different types of domination and graph products. We also give an improvement of the Clark-Suen inequality. Some partial results about fair domination are presented, and we summarize some open problems related to Vizing's conjecture.

A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Let G be a connected spanning subgraph of Ks,s, and let H be the complement of G relative to Ks,s; that is, Ks,s, = G ⊕ H is a factorization of Ks,s. The graph G is k-supercritical relative to Ks,s, if γt(G) = k and γ1(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.

Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles