# 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