Skip to main content

Circular flow and circular chromatic number in the matroid context

Resource type
Thesis type
(Thesis) Ph.D.
Date created
2007
Authors/Contributors
Abstract
This thesis considers circular flow-type and circular chromatic-type parameters ($\phi$ and $\chi$, respectively) for matroids. In particular we focus on orientable matroids and sixth root of unity matroids. These parameters are obtained via two approaches: algebraic and orientation-based. The general questions we discuss are: bounds for flow number; characterizations of Eulerian and bipartite matroids; and possible connections between the two possible extensions of $\phi$: algebraic and orientation. In the case of orientable matroids, we obtain characterizations of bipartite rank-3 matroids and Eulerian uniform, rank-3 matroids; an asymptotic result regarding the flow number of uniform matroids; and an improvement on the known bound for flow number of matroids of arbitrary rank. This bound is further improved for the uniform case. For sixth root of unity matroids, we examine an algebraic extension of the parameters $\chi$ and $\phi$. We also introduce a notion of orientation and the corresponding flow and chromatic numbers applicable to this class. We investigate the possibility of a connection between the algebraic and orientation-based parameters, akin to that established for regular matroids by Hoffman's Circulation Lemma and we obtain a partial connection. We extend the notion of ``Eulerian'' to sixth root of unity matroids. We call such matroids hex-Eulerian. We show that every maximum-sized sixth root of unity matroid, of fixed rank, is hex-Eulerian. We also show that a regular matroid is hex-Eulerian if and only if it admits a nowhere-zero 3-flow. We include an extension of Tutte's chain groups, which characterize regular matroids, to what we term hex-chain modules which describe sixth root of unity matroids.
Document
Copyright statement
Copyright is held by the author.
Permissions
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Download file Size
etd2859.pdf 1.3 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 0