2026-09-20T08:33:15Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/129306 2025-10-20 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms The student, Jingwei Xu, accepted the attached license on 2025-05-02 at 08:23. The student, Jingwei Xu, submitted this Dissertation for approval on 2025-05-02 at 08:30. This Dissertation was approved for publication on 2025-05-02 at 14:32. DSpace SAF Submission Ingestion Package generated from Vireo submission #22172 on 2025-10-19 at 18:11:32 Colorings of sparse graphs and multigraphs Xu, Jingwei 2025-05-02 Kostochka, Alexandr V. West, Douglas B. Methuku, Abhishek Bradshaw, Peter Graph coloring DP-coloring Defective coloring Edge-coloring eng This dissertation investigates several extremal problems in graph theory, focusing on graph density under vertex coloring constraints, and upper bounds on the number of colors required for injective edge-colorings in graphs with given maximum degree. A graph $G$ is $k$-critical (list $k$-critical, DP $k$-critical) if $\chi(G)= k$ ($\chi_\ell(G)= k$, $\cDP(G)= k$) and for every proper subgraph $G'$ of $G$, $\chi(G')<k$ ($\chi_\ell(G')< k$, $\cDP(G')<k$). % Let $f(n, k)$ ($f_\ell(n, k), \fDP(n,k)$) denote the minimum number of edges in an $n$-vertex $k$-critical (list $k$-critical, DP $k$-critical) graph. We establish new lower bounds on $\fDP(n,k)$ for all $k\geq 4, n\geq k+2$. These results provide the first asymptotic improvement over $\fDP(n,k)$ implied by the well-known lower bound on $f(n,k)$ by Gallai in 1963, and, in turn, yield improved lower bounds on $f_{\ell}(n,k)$ compared to previously known results. For nonnegative integers $i, j$ and a graph $G$, $G$ is $(i,j)$-colorable if $V(G)$ can be partitioned into two parts $V_1, V_2$, such that the maximum degrees of the induced subgraphs $G[V_1], G[V_2]$ are at most $i$ and $j$, respectively. $G$ is $(i,j)$-critical if $G$ is not $(i,j)$-colorable, but every proper subgraph of $G$ is. We present a new lower bound on the maximum average degree of $(1,3)$-critical graphs. We also introduce and study the concept of defective DP-coloring by combining ideas from defective colorings and DP-colorings. Let $f_{DP}(i,j,n)$ and $g_{DP}(i,j,n)$ denote the minimum number of edges that may have in an $n$-vertex, DP-$(i,j)$-critical multigraph and simple graph, respectively. For every $i$ and $j$, we show lower bounds on $f_{DP}(i,j,n)$ that are tight for infinitely many $n$. We show lower bounds on $g_{DP}(i,j,n)$ that are sharp for infinitely many $n$ for some pairs of $i,j$. Finally, we study edge-colorings. An edge-coloring $\phi$ of a graph $G$ is injective if for every pair of distinct edges $e_1, e_2\in E(G)$ that are in a common triangle or at distance one, $\phi(e_1)\neq \phi(e_2)$. Let $\chi'_{\rm {inj}}(G)$ denote the injective chromatic index of $G$, the minimum number of colors needed for an injective edge-coloring. We study how large $\chi'_{\rm {inj}}(G)$ can be in terms of the maximum degree of $G$, under constraints on the girth and/or chromatic number of $G$. We also compare our bounds with analogous bounds on the strong chromatic index. 2025-05 Thesis https://hdl.handle.net/2142/129306 Copyright 2025 Jingwei Xu Mathematics Mathematics University of Illinois Urbana-Champaign Ph.D. Dissertation