#### Title

On a Min-Max Property of Chordal Bipartite Graphs

#### Presenter(s)

Kayte Lynn Jackson

#### Files

#### Description

I will be exploring an interesting min-max feature of a subset of graphs called chordal bipartite graphs, those without any induced cycles on 6 or more vertices. First, I will explain special properties of a larger subset of bipartite graphs, those with no induced cycles on strictly 6 vertices, and how this leads to the conclusion for chordal bipartite graphs. The findings that are described are from a paper titled "A Min–Max Property of Chordal Bipartite Graphs with Applications" that I have read in detail. Consider a graph G, a bipartite graph with no induced cycles on exactly 6 vertices, then G* is the complement of the square of the line graph of G. The paper initially proves two facts. First, it proves that each maximal independent set of G* is the edge set of a chain subgraph of G. It also proves that the minimum number of chain subgraphs needed to cover the edges of G is equal to the chromatic number of G*. These fascinating properties along with a previous discovery that a chordal bipartite graph G has a weakly chordal G* leads to the conclusion that the size of the largest induced matching of G, the largest clique size of G*, the chromatic number of G*, and the minimum number of chain graphs needed to cover the edges of G are all equal in chordal bipartite graphs.

#### Publication Date

4-22-2021

#### Project Designation

Capstone Project

#### Primary Advisor

Atif A. Abueida, R. Sritharan

#### Primary Advisor's Department

Mathematics

#### Keywords

Stander Symposium project, College of Arts and Sciences

#### Recommended Citation

"On a Min-Max Property of Chordal Bipartite Graphs" (2021). *Stander Symposium Projects*. 2215.

https://ecommons.udayton.edu/stander_posters/2215