Five topics in extremal and structural graph theory

An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. We prove that G has an interval coloring using six colors when G is a (3, 4)-biregular bipartite graph having a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in {2, 4, 6, 8}. We also introduce a new variation of the interval coloring problem, wrapped coloring.;We study conditions under which subgraphs with maximum degree 1 or 2 of d-regular bipartite graphs extend to 1-factors or 2-factors. We prove that if M is a matching in Qd with at most k(d - k) edges and there is no deficient set of size less than k in the graph that remains when the endpoints of M are removed from Qd, then M extends to a 1-factor. This strengthens and generalizes a result of Limaye and Sarvate. We also show that if H is a subgraph of Qd with at most 2d - 3 edges and maximum degree 2, then H extends to a 2-factor. Moving beyond the d-dimensional hypercube, we give a Tutte-like necessary and sufficient condition in regular bipartite graphs for a subgraph H with maximum degree at most 2 to extend to a 2-factor. We provide several applications of this condition, particularly for the case when H is a matching.;The independence ratio of a graph is the fraction of vertices contained in a largest independent set. We study this for 2-factor-plus-triangles graphs, a class of graphs that generalizes cycle-plus-triangles graphs. Unlike cycle-plus-triangles graphs, these graphs may have independence ratio less than 1/3. We prove that the independence ratio of any 2-factor-plus-triangles graph is at least 1/4. We construct infinitely many connected 2-factor-plus-triangles graphs with independence ratio less than 4/15 and conjecture that 4/15 is the smallest value for which this is possible.;A p-page embedding of G is a vertex-ordering pi of V(G) (along the "spine" of a book) and an assignment of edges to p half-planes (called "pages") such that no page contains crossing edges. The pagenumber of G is the least p such that G has a p-page embedding. We show that for all k ≥ 3, there are k-trees that do not embed in k pages; this disproves a conjecture of Ganley and Heath. On the other hand, we present an algorithm that produces k-page embeddings for a special class of k-trees.;The Friendship Theorem states that if G is a graph in which every two vertices have exactly one common neighbor, then G has a dominating vertex. Sos defined an analogous friendship property for 3-uniform hypergraphs, and constructed a family satisfying it. We present additional 3-uniform hypergraphs on 8, 16, and 32 vertices that satisfy this property that were obtained using integer programming. No examples outside the family construct by Sos were previously known.