Tools for counting odd cycles in graphs
Review articleOpen access
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

References (0)

Cited By (0)

No reference data.
No citation data.
Advertisement
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!