Colorings of sparse graphs and multigraphs

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₁, V₂, such that the maximum degrees of the induced subgraphs G[V₁], G[V₂] 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₁, e₂\in E(G) that are in a common triangle or at distance one, \phi(e₁)\neq \phi(e₂). 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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Xu, Jingwei

Contributors dc:contributor

• Kostochka, Alexandr V.
• West, Douglas B.
• Methuku, Abhishek
• Bradshaw, Peter

• Graph coloring
• DP-coloring
• Defective coloring
• Edge-coloring

Statement dc:rights

• Copyright 2025 Jingwei Xu

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129306

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129306