Files in this item
Files  Description  Format 

application/pdf LIUDISSERTATION2020.pdf (2MB)  (no description provided) 
Description
Title:  Extremal problems on special graph colorings 
Author(s):  Liu, Xujun 
Director of Research:  Kostochka, Alexandr 
Doctoral Committee Chair(s):  Balogh, József 
Doctoral Committee Member(s):  Lavrov, Mikhail; Milenkovic, Olgica; West, Douglas 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  graph theory
combinatorics extremal graph theory graph colorings paths cycles connected matchings packing colorings packing chromatic number subcubic graphs independent sets independence ratio Ramsey number regularity lemma directed intersection number directed intersection representation directed graphs 
Abstract:  In this thesis, we study several extremal problems on graph colorings. In particular, we study monochromatic connected matchings, paths, and cycles in 2edge colored graphs, packing colorings of subcubic graphs, and directed intersection number of digraphs. In Chapter 2, we consider monochromatic structures in 2edge colored graphs. A matching M in a graph G is connected if all the edges of M are in the same component of G. Following Łuczak, there are a number of results using the existence of large connected matchings in cluster graphs with respect to regular partitions of large graphs to show the existence of long paths and other structures in these graphs. We prove exact Ramseytype bounds on the sizes of monochromatic connected matchings in 2edgecolored multipartite graphs. In addition, we prove a stability theorem for such matchings, which is used to find necessary and sufficient conditions on the existence of monochromatic paths and cycles: for every fixed s and large n, we describe all values of n_1, ...,n_s such that for every 2edgecoloring of the complete spartite graph K_{n_1, ...,n_s} there exists a monochromatic (i) cycle C_{2n} with 2n vertices, (ii) cycle C_{at least 2n} with at least 2n vertices, (iii) path P_{2n} with 2n vertices, and (iv) path P_{2n+1} with 2n+1 vertices. Our results also imply for large n of the conjecture by Gyárfás, Ruszinkó, Sárkőzy and Szemerédi that for every 2edgecoloring of the complete 3partite graph K_{n,n,n} there is a monochromatic path P_{2n+1}. Moreover, we prove that for every sufficiently large n, if n = 3t+r where r in {0,1,2} and G is an nvertex graph with minimum degree at least (3n1)/4, then for every 2edgecoloring of G, either there are cycles of every length {3, 4, 5, ..., 2t+r} of the same color, or there are cycles of every even length {4, 6, 8, ..., 2t+2} of the same color. This result is tight and implies the conjecture of Schelp that for every sufficiently large n, every (3n1)vertex graph G with minimum degree larger than 3V(G)/4, in each 2edgecoloring of G there exists a monochromatic path P_{2n} with 2n vertices. It also implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for every positive integer n of the form n=3t+r where r in {0,1,2} and every nvertex graph G with minimum degree at least 3n/4, in each 2edgecoloring of G there exists a monochromatic cycle of length at least 2t+r. In Chapter 3, we consider a collection of special vertex colorings called packing colorings. For a sequence of nondecreasing positive integers S = (s_1, ..., s_k), a packing Scoloring is a partition of V(G) into sets V_1, ..., V_k such that for each integer i in {1, ..., k} the distance between any two distinct x,y in V_i is at least s_i+1. The smallest k such that G has a packing (1,2, ..., k)coloring is called the packing chromatic number of G and is denoted by \chi_p(G). The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We show that for every fixed k and g at least 2k+2, almost every nvertex cubic graph of girth at least g has the packing chromatic number greater than k, which answers the previous question in the negative. Moreover, we work towards the conjecture of Brešar, Klavžar, Rall and Wash that the packing chromatic number of 1subdivision of subcubic graphs are bounded above by 5. In particular, we show that every subcubic graph is (1,1,2,2,3,3,k)colorable for every integer k at least 4 via a coloring in which color k is used at most once, every 2degenerate subcubic graph is (1,1,2,2,3,3)colorable, and every subcubic graph with maximum average degree less than 30/11 is packing (1,1,2,2)colorable. Furthermore, while proving the packing chromatic number of subcubic graphs is unbounded, we also consider improving upper bound on the independence ratio, alpha(G)/n, of cubic nvertex graphs of large girth. We show that ``almost all" cubic labeled graphs of girth at least 16 have independence ratio at most 0.454. In Chapter 4, we introduce and study the directed intersection representation of digraphs. A directed intersection representation is an assignment of a color set to each vertex in a digraph such that two vertices form an edge if and only if their color sets share at least one color and the tail vertex has a strictly smaller color set than the head. The smallest possible size of the union of the color sets is defined to be the directed intersection number (DIN). We show that the directed intersection representation is welldefined for all directed acyclic graphs and the maximum DIN among all n vertex acyclic digraphs is at most 5n^2/8 + O(n) and at least 9n^2/16 + O(n). 
Issue Date:  20200708 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/108445 
Rights Information:  Copyright 2020 Xujun Liu 
Date Available in IDEALS:  20201007 
Date Deposited:  202008 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois