Jessica McDonald

Restricting Odd Antiholes in Critical Graphs via List Coloring

Alireza Fiujlaali, Jessica McDonald

By the Strong Perfect Graph Theorem, every graph whose chromatic number exceeds its clique number contains an odd hole or an odd antihole. We investigate the structure of odd antih…

Towards the Overfull Conjecture II

Guantao Chen, Jessica McDonald, Songling Shan

Let $G$ be a simple graph with maximum degree $Δ (G)$ . A subgraph $H \subseteq G$ is $Δ (G)$ -overfull if $∣ E (H) ∣ > Δ (G) ⌊ ∣ V (H) ∣/2 ⌋$ . In any edge coloring of $G$ ,…

Coloring graphs with independence number two and no odd clique immersions

Henry Echeverría, Jessica McDonald

We study the chromatic number of graphs that exclude a clique as a strong odd immersion and have independence number two. Given a graph $G$ and $t \in Z^{+}$ , we prove that if…

On graphs with girth at least five achieving Steffen's edge coloring bound

Guantao Chen, Alireza Fiujlaali, Anna Johnsen-Yu +1

Vizing and Gupta showed that the chromatic index $χ^{'} (G)$ of a graph $G$ is bounded above by $Δ (G) + μ (G)$ , where $Δ (G)$ and $μ (G)$ denote the maximum degree and the maximum multipl…

Degree sequences realizing labelled perfect matchings

Joseph Briggs, Jessica McDonald, Songling Shan

Let $n \in N$ and $d_{1} \geq d_{2} \geq d_{n} \geq 1$ be integers. There is characterization of when $(d_{1}, d_{1}, \dots, d_{n})$ is the degree sequence of a graph containing a perf…

Extending total colorings in planar graphs

Owen Henderschedt, Jessica McDonald

We initiate the study of total-coloring extensions, and focus our attention on planar graphs, asking: ``When can a total- $k$ -coloring of some subgraph $H$ of a planar graph $G$ be…

Cliques and High Odd Holes in Graphs with Chromatic Number Equal to Maximum Degree

Rachel Galindo, Jessica McDonald, Songling Shan

We give a uniform and self-contained proof that if $G$ is a connected graph with $χ (G) = Δ (G)$ and $G \neq = C_{7}$ , then $G$ contains either $K_{Δ (G)}$ or an odd hole where…

Total coloring graphs with large minimum degree

Owen Henderschedt, Jessica McDonald, Songling Shan

We prove that for all $ε > 0$ , there exists a positive integer $n_{0}$ such that if $G$ is a graph on $n \geq n_{0}$ vertices with $δ (G) \geq \frac{1}{2} (1 + ε) n$ , then…

Maximizing the number of stars in graphs with forbidden properties

Zhanar Berikkyzy, Kirsten Hogenson, Rachel Kirsch +1

Erdős proved an upper bound on the number of edges in an $n$ -vertex non-Hamiltonian graph with given minimum degree and showed sharpness via two members of a particular graph famil…

On graphs with chromatic number and maximum degree both equal to nine

Rachel Galindo, Jessica McDonald

An equivalent version of the Borodin-Kostochka Conjecture, due to Cranston and Rabern, says that any graph with $χ = Δ = 9$ contains $K_{3} \lor E_{6}$ as a subgraph. Here we prove sever…

A reduction of the "cycles plus $K_{4}$ 's" problem

Aseem Dalal, Jessica McDonald, Songling Shan

Let $H$ be a 2-regular graph and let $G$ be obtained from $H$ by gluing in vertex-disjoint copies of $K_{4}$ . The "cycles plus $K_{4}$ 's" problem is to show that $G$ is 4-colourable; t…

On orientations with forbidden out-degrees

Owen Henderschedt, Jessica McDonald

Let $G$ be a $d$ -regular graph and let $F \subseteq {0, 1, 2, \dots, d}$ be a list of forbidden out-degrees. Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati conjectured that if…