Odd induced subgraphs in graphs with treewidth at most two

DOI10.1007/S00373-018-1892-XMaRDI QIDQ2413620zbMATH OpenOpenAlexFDO

Authors Xinmin Hou, Lei Yu, Jiaao Li, Boyuan Liu

Publication date 14 September 2018

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.04812

zbMATH Keywords

treewidthinduced subgraphodd graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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)|/(2chi(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/(2chi(G))$ seems to be not best possible, for example, Radcliffe and Scott (1995) proved $c=frac23$ for trees, Berman, Wang and Wargo (1997) showed that $c=frac25$ 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=frac25$, and the bound is best possible.

Recommendations

• Odd induced subgraphs in planar graphs with large girth
• Every tree contains a large induced subgraph with all degrees odd
• Every graph contains a linearly sized induced subgraph with all degrees odd
• On induced subgraphs of trees, with restricted degrees
• Large Induced Subgraphs with All Degrees Odd

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 1051278 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Coloring the square of a \(K_{4}\)-minor free graph
• Every tree contains a large induced subgraph with all degrees odd
• Large Induced Subgraphs with All Degrees Odd
• On induced subgraphs with odd degrees

Cited in

(6)

• Odd induced subgraphs in planar graphs with large girth
• Graphs whose the maximum size of an odd subgraph equal to \(\lfloor \frac{n}{2} \rfloor \)
• Maximum odd induced subgraph of a graph concerning its chromatic number
• Induced subgraphs of a tree with constraint degree
• On the complexity of finding large odd induced subgraphs and odd colorings
• On the chromatic number of (P_{5},windmill)-free graphs

This page was built for publication: Odd induced subgraphs in graphs with treewidth at most two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413620)