pith. machine review for the scientific record. sign in

arxiv: 1707.04812 · v1 · submitted 2017-07-16 · 🧮 math.CO

Recognition: unknown

Odd induced subgraphs in graphs with treewidth at most two

Authors on Pith no claims yet
classification 🧮 math.CO
keywords graphsconjecturefracinducedorderbestchromaticdegrees
0
0 comments X
read the original abstract

A long-standing conjecture asserts that there exists a constant $c>0$ such that every graph of order $n$ without isolated vertices contains an induced subgraph of order at least $cn$ with all degrees odd. Scott (1992) proved that every graph $G$ has an induced subgraph of order at least $|V(G)|/(2\chi(G))$ with all degrees odd, where $\chi(G)$ is the chromatic number of $G$, this implies the conjecture for graphs with { bounded} chromatic number. But the factor $1/(2\chi(G))$ seems to be not best possible, for example, Radcliffe and Scott (1995) proved $c=\frac 23$ for trees, Berman, Wang and Wargo (1997) showed that $c=\frac 25$ for graphs with maximum degree $3$, so it is interesting to determine the exact value of $c$ for special family of graphs. In this paper, we further confirm the conjecture for graphs with treewidth at most 2 with $c=\frac{2}{5}$, and the bound is best possible.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.