Bipartite subgraphs of triangle-free subcubic graphs

DOI10.1016/j.jctb.2008.04.005zbMath1185.05084MaRDI QIDQ2519015

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

triangle-free; bipartite density; independence ratio; subcubic; bipartite ratio

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C07: Vertex degrees

Related Items

Subcubic triangle-free graphs have fractional chromatic number at most 14/5, 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, Independence, odd girth, and average degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge density and independence ratio in triangle-free graphs with maximum degree three
• Triangle-free subcubic graphs with minimum bipartite density
• The Fractional Chromatic Number of Graphs of Maximum Degree at Most Three
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Some Ramsey-Type Numbers and the Independence Ratio
• Maximumk-colorable subgraphs
• Extremal bipartite subgraphs of cubic triangle-free graphs
• Size and independence in triangle‐free graphs with maximum degree three
• Node-and edge-deletion NP-complete problems
• A new proof of the independence ratio of triangle-free cubic graphs