Large Induced Subgraphs with All Degrees Odd

DOI10.1017/S0963548300000389MaRDI QIDQ4291193zbMATH OpenOpenAlexFDO

Authors Alex 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

chromatic numberconnected graphinduced subgraphboundrandom graphs

Mathematics Subject Classification ID

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

Recommendations

• Every graph contains a linearly sized induced subgraph with all degrees odd
• Every tree contains a large induced subgraph with all degrees odd
• On induced subgraphs with odd degrees
• On induced subgraphs with all degree odd

Cited in

(19)

• Distinct degrees and homogeneous sets
• Every tree contains a large induced subgraph with all degrees odd
• Odd induced subgraphs in planar graphs with large girth
• Note on Perfect Forests
• Odd induced subgraphs in graphs with treewidth at most two
• Unavoidable Induced Subgraphs of Large 2-Connected Graphs
• Large induced subgraphs with equated maximum degree
• On induced subgraphs with odd degrees
• 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
• Every graph contains a linearly sized induced subgraph with all degrees odd
• Isolating highly connected induced subgraphs
• Maximum odd induced subgraph of a graph concerning its chromatic number
• Induced subgraphs of a tree with constraint degree
• A result on large induced subgraphs with prescribed residues in bipartite graphs
• On the complexity of finding large odd induced subgraphs and odd colorings
• Large induced subgraphs with three repeated degrees
• On induced subgraphs with all degree odd
• All trees contain a large induced subgraph having all degrees 1 (mod \(k\))

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

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