Michael C. Wigal

activity

20172025

most citedLarge cycles in essentially 4-connected graphs

1 citations · 1 across the 15 of their papers we have counts for

collaborators

Showing math.COShow all

15 papers · 1 filter

math.CO2025

Toward Vu's conjecture

Peter Bradshaw, Abhishek Dhawan, Abhishek Methuku +1

In 2002, Vu conjectured that graphs of maximum degree $Δ$ and maximum codegree at most $ζ Δ$ have chromatic number at most $(ζ + o (1)) Δ$ . Despite its importance, the conjecture has re…

math.CO2025

Turán densities for matroid basis hypergraphs

Jorn van der Pol, Zach Walsh, Michael C. Wigal

Let $U$ be a uniform matroid. For all positive integers $n$ and $r$ with $n \geq r$ , what is the maximum number of bases of an $n$ -element, rank- $r$ matroid without $U$ as a minor?…

math.CO2025

Packing edge disjoint cliques in graphs

József Balogh, Michael C. Wigal

Let $r \geq 3$ be fixed and $G$ be an $n$ -vertex graph. A long-standing conjecture of Győri states that if $e (G) = t_{r - 1} (n) + k$ , where $t_{r - 1} (n)$ denotes the number of edges of…

math.CO2024

Longest Path and Cycle Transversals in Chordal Graphs

James A. Long, Kevin G. Milans, Michael C. Wigal

We show that if $G$ is a $n$ -vertex connected chordal graph, then it admits a longest path transversal of size $O (lo g^{2} n)$ . Under the stronger assumption of 2-connectivity, we sh…

math.CO2024

Clique covers and decompositions of cliques of graphs

József Balogh, Jialin He, Robert A. Krueger +2

In 1966, Erdős, Goodman, and Pósa showed that if $G$ is an $n$ -vertex graph, then at most $⌊ n^{2} /4 ⌋$ cliques of $G$ are needed to cover the edges of $G$ , and the bound…

math.CO2024

On the number of $P$ -free set systems for tree posets $P$

József Balogh, Ramon I. Garcia, Michael C. Wigal

We say a finite poset $P$ is a tree poset if its Hasse diagram is a tree. Let $k$ be the length of the largest chain contained in $P$ . We show that when $P$ is a fixed tree poset,…

math.CO2024

The Cordiality Game and the Game Cordiality Number

Elliot Krop, Aryan Mittal, Michael C. Wigal

The cordiality game is played on a graph $G$ by two players, Admirable (A) and Impish (I), who take turns selecting \track{unlabeled} vertices of $G$ . Admirable labels the selected…

math.CO2023

Improving Uniquely Decodable Codes in Binary Adder Channels

József Balogh, The Nguyen, Patric R. J. Ostergard +2

We present a general method to modify existing uniquely decodable codes in the $T$ -user binary adder channel. If at least one of the original constituent codes does not have averag…

math.CO2023

Sampling planar tanglegrams and pairs of disjoint triangulations

Alexander E. Black, Kevin Liu, Alex Mcdonough +4

A tanglegram consists of two rooted binary trees and a perfect matching between their leaves, and a planar tanglegram is one that admits a layout with no crossings. We show that th…

math.CO2021

Approximating TSP walks in subcubic graphs

Michael C. Wigal, Youngho Yoo, Xingxing Yu

We prove that every simple 2-connected subcubic graph on $n$ vertices with $n_{2}$ vertices of degree 2 has a TSP walk of length at most $\frac{5 n + n _{2}}{4} - 1$ , confirming a conjecture…

math.CO2021

On Tutte cycles containing three prescribed edges

Michael C. Wigal, Xingxing Yu

A cycle $C$ in a graph $G$ is called a Tutte cycle if, after deleting $C$ from $G$ , each component has at most three neighbors on $C$ . Tutte cycles play an important role in the st…

math.CO2020★ 1 cited

Large cycles in essentially 4-connected graphs

Michael Wigal, Xingxing Yu

Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but there are 3-connected $n$ -vertex planar graphs whose longest cycles have length $Θ (n^{l o g_{3} 2})$ . On…

math.CO2018

A Dichotomy Theorem for First-Fit Chain Partitions

Kevin G. Milans, Michael C. Wigal

First-Fit is a greedy algorithm for partitioning the elements of a poset into chains. Let $FF (w, Q)$ be the maximum number of chains that First-Fit uses on a $Q$ -free poset…

math.CO2017

Online coloring a token graph

Kevin G. Milans, Michael C. Wigal

We study a combinatorial coloring game between two players, Spoiler and Algorithm, who alternate turns. First, Spoiler places a new token at a vertex in $G$ , and Algorithm responds…

math.CO2017

Ordered multiplicity inverse eigenvalue problem for graphs on six vertices

John Ahn, Christine Alar, Beth Bjorkman +6

For a graph $G$ , we associate a family of real symmetric matrices, $S (G)$ , where for any $M \in S (G)$ , the location of the nonzero off-diagonal entries of $M$ a…

Toward Vu's conjecture

Turán densities for matroid basis hypergraphs

Packing edge disjoint cliques in graphs

Longest Path and Cycle Transversals in Chordal Graphs

Clique covers and decompositions of cliques of graphs

On the number of P-free set systems for tree posets P

The Cordiality Game and the Game Cordiality Number

Improving Uniquely Decodable Codes in Binary Adder Channels

Sampling planar tanglegrams and pairs of disjoint triangulations

Approximating TSP walks in subcubic graphs

On Tutte cycles containing three prescribed edges

Large cycles in essentially 4-connected graphs

A Dichotomy Theorem for First-Fit Chain Partitions

Online coloring a token graph

Ordered multiplicity inverse eigenvalue problem for graphs on six vertices

On the number of $P$ -free set systems for tree posets $P$