Events
DMS Combinatorics Seminar |
| Time: Jan 14, 2021 (02:00 PM) |
| Location: ZOOM |
|
Details: Speaker: Pete Johnson Title: Progress in Finding Critically PRCF-Bad Graphs
Abstract: A proper rainbow-cycle-forbidding (PRCF) coloring of a graph is a proper edge-coloring which forbids rainbow cycles; this last means that for every cycle in the graph, at least one color appears at least twice on the cycle. A graph is PRCF-good if it has a PRCF coloring; otherwise it is PRCF-bad. Clearly every subgraph of a PRCF-good graph is PRCF-good. This implies that the PRCF-good graphs have a forbidden subgraph characterization, which means that there is a family FAM of graphs such that a graph G is PRCF-good if and only if G has no element of FAM as a subgraph. Obviously the family of all PRCF-bad graphs will serve as such a characterizing family for the PRCF-good graphs, but the gold under the rubble would be the smallest such family, the family of critically PRCF-bad graphs. G is critically PRCF-bad if it is PRCF-bad but every proper subgraph of G is PRCF-good. In our early adventures with PRCF colorings we knew of only two critically PRCF-bad graphs, K_3 and K(2,4). Then Andy Owens somehow found one with 7 vertices, and Greg Puleo found a few, with up to 12 vertices, with the aid of a computer. The few that we do have make us despair of any succinct description of these things, but we would like to answer a couple of questions about them:
The talk will be about two different promising attacks on question 1, one due to Nico Terry and the other to Matt Noble.
Dean Hoffman is inviting you to a scheduled Auburn University Zoom e-meeting. |