132 research outputs found
Higher Education
No full text<p>Conference paper on Quality of Eduaction at Addis Ababa University. The paper was presented by Yared Nigussie at the annual conference of Ethiopian Statistical Association in the United Nations Conference Room,Addis Ababa</p
Extended Gallai\u27s Theorem
No full textLet 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\u27s 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\u27s Theorem holds
Density of universal classes of series-parallel graphs
No full textA class of graphs C ordered by the homomorphism relation is universal if every countable partial order can be embedded in C. It was shown in [1] that the class Ck of k-colorable graphs, for any fixed k ≥ 3, induces a universal partial order. In [4], a surprisingly small subclass of C3 which is a proper subclass of K4-minor-free graphs (G/K4) is shown to be universal. In another direction, a density result was given in [9], that for each rational number a/b ∈ [2, 8/3] ∪ {3}, there is a K4-minor-free graph with circular chromatic number equal to a/b. In this note we show for each rational number a/b within this interval the class Ka/b of K4-minor-free graphs with circular chromatic number a/b is universal if and only if a/b � = 2, 5/2 or 3. This shows yet another surprising richness of the K4-minor-free class that it contains universal classes as dense as the rational numbers
Algorithm for finding structures and obstructions of tree ideals
No full textAbstractLet I be any topological minor closed class of trees (a tree ideal). A classical theorem of Kruskal [Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture, Trans. Am. Math. Soc. 95 (1960) 210–223] states that the set O(I) of minimal non-members of I is finite. On the other hand, a finite structural description S(I) is developed by Robertson, et al. [Structural descriptions of lower ideals of trees, Contemp. Math. 147 (1993) 525–538]. Given either of the two finite characterizations of I, we present an algorithm that computes the other
Short proofs for two theorems of Chien, Hell and Zhu
No full textIn (J Graph Theory 33 (2000), 14-24), Hell and Zhu proved that if a series-parallel graph G has girth at least 2⌊(3k-1)/2⌋, then χc(G)≤4k/(2k-1). In (J Graph Theory 33 (2000), 185-198), Chien and Zhu proved that the girth condition given in (J Graph Theory 33 (2000), 14-24) is sharp. Short proofs of both results are given in this note
Finite dualities and map-critical graphs on a fixed surface
No full textAbstractLet 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
Density of universal classes of series-parallel graphs
No full textA class of graphs ordered by the homomorphism relation is universal if every countable partial order can be embedded in . It was shown in [ZH] that the class of -colorable graphs, for any fixed , induces a universal partial order. In [HN1], a surprisingly small subclass of which is a proper subclass of -minor-free graphs is shown to be universal. In another direction, a density result was given in [PZ], that for each rational number , there is a -minor-free graph with circular chromatic number equal to . In this note we show for each rational number within this interval the class of -minor-free graphs with circular chromatic number is universal if and only if , or . This shows yet another surprising richness of the -minor-free class that it contains universal classes as dense as the rational numbers
On a new reformulation of Hadwiger’s conjecture
No full textAssuming that every proper minor closed class of graphs contains a maximum with respect to the homomorphism order, we prove that such a maximum must be homomorphically equivalent to a complete graph. This proves that Hadwiger’s conjecture is equivalent to saying that every minor closed class of graphs contains a maximum with respect to homomorphism order. Let F be a finite set of 2-connected graphs, and let C be the class of graphs with no minor from F. We prove that if C has a maximum, then any maximum of C must be homomorphically equivalent to a complete graph. This is a special case of a conjecture of J. Neˇsetˇril and P. Ossona de Mendez
Finite Duality for Some Minor Closed Classes
No full textLet K be a class of finite graphs and F = {F1, F2, ..., Fm} be a set of finite graphs. Then, K is said to have finite-duality if there exists a graph U in K such that for any graph G in K, G is homomorphic to U if and only if Fi is not homomorphic to G, for all i = 1, 2, ..., m. Nešetřil asked in [J. Nešetřil, Homonolo Combinatorics Workshop, Nova Louka, Czech Rep., (2003)] if non-trivial examples can be found. In this note, we answer this positively by showing classes containing arbitrary long anti-chains and yet having the finite-duality property
- …
