Bipartite subgraphs of triangle-free subcubic graphs

DOI10.1016/J.JCTB.2008.04.005MaRDI QIDQ2519015zbMATH OpenOpenAlexFDO

Authors Xuding Zhu

Publication date 21 January 2009

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2008.04.005

zbMATH Keywords

bipartite densitybipartite ratioindependence ratiosubcubictriangle-free

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Bipartite density of triangle-free subcubic graphs
• Triangle-free subcubic graphs with minimum bipartite density
• Maximum bipartite subgraphs of cubic triangle-free planar graphs
• Bipartite density of cubic graphs
• Dense induced bipartite subgraphs in triangle-free graphs

Cites work

• A new proof of the independence ratio of triangle-free cubic graphs
• Edge density and independence ratio in triangle-free graphs with maximum degree three
• Extremal bipartite subgraphs of cubic triangle-free graphs
• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• scientific article; zbMATH DE number 3706475 (Why is no real title available?)
• scientific article; zbMATH DE number 3715594 (Why is no real title available?)
• scientific article; zbMATH DE number 3536160 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Maximumk-colorable subgraphs
• Node-and edge-deletion NP-complete problems
• Size and independence in triangle‐free graphs with maximum degree three
• Some Ramsey-Type Numbers and the Independence Ratio
• The fractional chromatic number of graphs of maximum degree at most three
• Triangle-free subcubic graphs with minimum bipartite density

Cited in

(19)

• Maximum bipartite subgraphs of cubic triangle-free planar graphs
• Bipartite density of triangle-free subcubic graphs
• Bipartite subgraphs of graphs with maximum degree three
• Bipartite subgraphs of integer weighted graphs
• New formulae for the bipartite vertex frustration and decycling number of graphs
• Nordhaus-Gaddum and other bounds for the chromatic edge-stability number
• Critical graphs for the chromatic edge-stability number
• Graphs in which all maximal bipartite subgraphs have the same order
• A note on bipartite subgraphs and triangle-independent sets
• Triangle-free subcubic graphs with minimum bipartite density
• Independence, odd girth, and average degree
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• A note on bipartite subgraphs of triangle‐free graphs
• Bipartite Subgraphs of Triangle-Free Graphs
• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)
• Small bipartite subgraph polytopes
• Monotonic decompositions of submodular set functions
• Bisections of directed graphs without complete bipartite subgraphs
• Lower bounds for maximum weight bisections of weighted triangle-free subcubic graphs

This page was built for publication: Bipartite subgraphs of triangle-free subcubic graphs

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