##### Tools for counting odd cycles in graphs

Review articleOpen access###### Donovan R. Hare - No affiliation found

**2019/04/01**DOI: 10.1016/j.jctb.2019.03.003

*Full-length article***Journal:**Journal of Combinatorial Theory, Series B

##### Abstract:

AbstractLet k be a positive integer at least 2. A graph is k-critical if it can be colored in no fewer than k colors and its proper subgraphs can be colored in fewer than k colors. T. Gallai asked whether a k-critical graph on n vertices contains n distinct (k−1)-critical subgraphs. This paper gives an affirmative answer to Gallai's question restricted to 4-critical graphs by proving they contain at least 83n−293 odd cycles.For 2-connected nonbipartite graphs, it is shown that the cycle space of such a graph is generated by its odd cycles and that its cyclomatic number provides a sharp lower bound for the number of its odd cycles.For 3-connected nonbipartite graphs, it is shown that the cycle space of such a graph is generated by the set of odd cycles containing any fixed vertex. An initially bipartite ear decomposition is described and is used to show that these graphs contain a spanning 2-connected bipartite subgraph, and contain at least as many odd cycles as the number of their vertices.

Request full text