{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129306"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129306","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Colorings of sparse graphs and multigraphs","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled &#x27;Open Access&#x27;. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_has_math":false,"creators":["Xu, Jingwei"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Kostochka, Alexandr V.","West, Douglas B.","Methuku, Abhishek","Bradshaw, Peter"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-05-02","date_published":"2025-05-02","updated_at":"2026-07-22T22:25:04Z","subjects":["Graph coloring","DP-coloring","Defective coloring","Edge-coloring"],"languages":["en","eng"],"rights":["Copyright 2025 Jingwei Xu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129306","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kostochka, Alexandr V.","West, Douglas B.","Methuku, Abhishek","Bradshaw, Peter"]},{"key":"dc:creator","label":"Author","values":["Xu, Jingwei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-05-02","2025-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph coloring","DP-coloring","Defective coloring","Edge-coloring"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Jingwei Xu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129306"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Colorings of sparse graphs and multigraphs"]}]}],"canonical_facts":{"dc:contributor":["Kostochka, Alexandr V.","West, Douglas B.","Methuku, Abhishek","Bradshaw, Peter"],"dc:creator":["Xu, Jingwei"],"dc:date":["2025-05-02","2025-05"],"dc:description":["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","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129306"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Jingwei Xu"],"dc:subject":["Graph coloring","DP-coloring","Defective coloring","Edge-coloring"],"dc:title":["Colorings of sparse graphs and multigraphs"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:04Z"}