Large Induced Subgraphs with All Degrees Odd

DOI10.1017/S0963548300000389zbMath0793.05089OpenAlexW2159873465MaRDI QIDQ4291193

Alexander D. Scott

Publication date: 5 May 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300000389

zbMATH Keywords

random graphschromatic numberboundinduced subgraphconnected graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Related Items (12)

Every tree contains a large induced subgraph with all degrees odd ⋮ Note on Perfect Forests ⋮ Every graph contains a linearly sized induced subgraph with all degrees odd ⋮ All trees contain a large induced subgraph having all degrees 1 (mod \(k\)) ⋮ Odd induced subgraphs in graphs with treewidth at most two ⋮ Odd induced subgraphs in planar graphs with large girth ⋮ On subgraphs with degrees of prescribed residues in the random graph ⋮ Counting partitions of Gn,1/2$$ {G}_{n,1/2} $$ with degree congruence conditions ⋮ Distinct degrees and homogeneous sets ⋮ A result on large induced subgraphs with prescribed residues in bipartite graphs ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Induced subgraphs of a tree with constraint degree

This page was built for publication: Large Induced Subgraphs with All Degrees Odd