On a Min-Max Property of Chordal Bipartite Graphs

On a Min-Max Property of Chordal Bipartite Graphs

Presenter(s)

Kayte Lynn Jackson

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

On a Min-Max Property of Chordal Bipartite Graphs

Share

COinS