Odd induced subgraphs in graphs with treewidth at most two

DOI10.1007/S00373-018-1892-XzbMATH Open1395.05111arXiv1707.04812OpenAlexW2964295158MaRDI QIDQ2413620FDOQ2413620

Jiaao Li, Boyuan Liu, Xinmin Hou, Lei Yu

Publication date: 14 September 2018

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

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.

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

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

zbMATH Keywords

treewidthinduced subgraphodd graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Coloring the square of a \(K_{4}\)-minor free graph
• Large Induced Subgraphs with All Degrees Odd
• On induced subgraphs with odd degrees
• Every tree contains a large induced subgraph with all degrees odd
• Title not available (Why is that?)

Cited In (5)

• Odd induced subgraphs in planar graphs with large girth
• 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)