Thesis (M.S.)--School of Mathematics, Georgia Institute of Technology, 2005. Directed by Xingxing Yu. / Xingxing Yu, Committee Chair ; Robin Thomas, Committee Member ; Prasad Tetali, Committee Member ; Anurag Singh, Committee Member. Includes bibliographical references.

Thesis (Ph. D.)--Ohio State University, 2005. / Title from first page of PDF file. Document formatted into pages; contains viii, 80 p.; also includes graphics. Includes bibliographical references (p. 80). Available online via OhioLINK's ETD Center

No description available.

Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. This thesis develops new techniques to prove general theorems for 5-list-coloring graphs embedded in a fixed surface. Indeed, a general paradigm is established which improves a number of previous results while resolving several open conjectures. In addition, the proofs are almost entirely self-contained. In what follows, let S be a fixed surface, G be a graph embedded in S and L a list assignment such that, for every vertex v of G, L(v) has size at least five. First, the thesis provides an independent proof of a theorem of DeVos, Kawarabayashi and Mohar that says if G has large edge-width, then G is 5-list-colorable. Moreover, the bound on the edge-width is improved from exponential to logarithmic in the Euler genus of S, which is best possible up to a multiplicative constant. Second, the thesis proves that there exist only finitely many 6-list-critical graphs embeddable in S, solving a conjecture of Thomassen from 1994. Indeed, it is shown that the number of vertices in a 6-list-critical graph is at most linear in genus, which is best possible up to a multiplicative constant. As a corollary, there exists a linear-time algorithm for deciding 5-list-colorability of graphs embeddable in S. Furthermore, we prove that the number of L-colorings of an L-colorable graph embedded in S is exponential in the number of vertices of G, with a constant depending only on the Euler genus g of S. This resolves yet another conjecture of Thomassen from 2007. The thesis also proves that if X is a subset of the vertices of G that are pairwise distance Omega(log g) apart and the edge-width of G is Omega(log g), then any L-coloring of X extends to an L-coloring of G. For planar graphs, this was conjectured by Albertson and recently proved by Dvorak, Lidicky, Mohar, and Postle. For regular coloring, this was proved by Albertson and Hutchinson. Other related generalizations are examined.

No description available.

In this thesis, we introduce the intersperse coloring problem, which is a generalized version of the hypergraph coloring problem. In the intersperse coloring problem, we seek a coloring that assigns at least l different colors to each hyperedge of the input hypergraph, where l is an input parameter of the problem. We show that the notion of intersperse coloring unifies several well-known coloring problems, in addition to the conventional graph and hypergraph coloring problems, such as the strong coloring of hypergraphs, the star coloring problem, the problem of proper coloring of graph powers, the acyclic coloring problem, and the frugal coloring problem. We also provide a number of upper and lower bounds on the intersperse coloring problem on hypergraphs in the general case. The nice thing about our general bounds is that they can be applied to all the coloring problems that are special cases of the intersperse coloring problem. In this thesis, we also propose a new model for graph and hypergraph property testing, called the symmetric model. The symmetric model is the first model that can be used for developing property testing algorithms for non-uniform hypergraphs. We also prove that there exist graph properties that have efficient property testers in the symmetric model but do not have any efficient property tester in previously-known property testing models.

In this thesis, we introduce the intersperse coloring problem, which is a generalized version of the hypergraph coloring problem. In the intersperse coloring problem, we seek a coloring that assigns at least l different colors to each hyperedge of the input hypergraph, where l is an input parameter of the problem. We show that the notion of intersperse coloring unifies several well-known coloring problems, in addition to the conventional graph and hypergraph coloring problems, such as the strong coloring of hypergraphs, the star coloring problem, the problem of proper coloring of graph powers, the acyclic coloring problem, and the frugal coloring problem. We also provide a number of upper and lower bounds on the intersperse coloring problem on hypergraphs in the general case. The nice thing about our general bounds is that they can be applied to all the coloring problems that are special cases of the intersperse coloring problem. In this thesis, we also propose a new model for graph and hypergraph property testing, called the symmetric model. The symmetric model is the first model that can be used for developing property testing algorithms for non-uniform hypergraphs. We also prove that there exist graph properties that have efficient property testers in the symmetric model but do not have any efficient property tester in previously-known property testing models.

No description available.

There has been extensive research activities in the last couple of years to efficiently determine large sparse Jacobian matrices. It is now well known that the estimation of Jacobian matrices can be posed as a graph coloring problem. Unidirectional coloring by Coleman and More [9] and bidirectional coloring independently proposed by Hossain and Steihaug [23] and Coleman and Verma [12] are techniques that employ graph theoretic ideas. In this thesis we present heuristic and exact bidirectional coloring techniques. For bidirectional heuristic techniques we have implemented variants of largest first ordering, smallest last ordering, and incidence degree ordering schemes followed by the sequential algorithm to determine the Jacobian matrices. A "good" lower bound given by the maximum number of nonzero entries in any row of the Jacobian matrix is readily obtained in an unidirectional determination. However, in a bidirectional determination no such "good" lower bound is known. A significant goal of this thesis is to ascertain the effectiveness of the existing heuristic techniques in terms of the number of matrix-vector products required to determine the Jacobian matrix. For exact bidirectional techniques we have proposed an integer linear program to solve the bidirectional coloring problem. Part of exact bidirectional coloring results were presented at the "Second International Workshop on Cominatorial Scientific Computing (CSC05), Toulouse, France." / viii, 83 leaves ; 29 cm.

Reed's conjecture is a proposed upper bound for the chromatic number of a graph. Reed's conjecture has already been proven for several families of graphs. In this paper, I show how one of those families of graphs can be extended to include additional graphs and also show that Reed's conjecture holds for a family of graphs known as cycle-power graphs, and also for their complements.