Maximum Bisections of Graphs Without Adjacent Quadrilaterals

被引：0

作者：

Hu, Qiming ^{[1
]}

Xu, Baogang ^{[1
]}

机构：

[1] Nanjing Normal Univ, Inst Math, Sch Math Sci, 1 Wenyuan Rd, Nanjing 210023, Peoples R China

来源：

GRAPHS AND COMBINATORICS | 2025年 / 41卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Bipartition; Bisection; C-6-free graphs; BIPARTITE SUBGRAPHS;

D O I：

10.1007/s00373-025-02889-7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let Ck be a cycle of length k . Let G be a graph with n vertices, m edges. Lin and Zeng proved that if G has a perfect matching and does not contain C-4 , C-6 and C-2k , then G admits a bisection of size at least m|2 + c(k)m((2k+1)/(2k+2)) and showed that the bound is tight for k E { 3 , 5}. In this paper, we obtain a similar tight result by replacing C-4 with two adjacent C-4's.

引用

页数：29

共 21 条

[1] Maximum bisections of graphs without cycles of length 4
Rao, Mengjiao
Hou, Jianfeng
Zeng, Qinghou
DISCRETE MATHEMATICS, 2022, 345 (08)
[2] Maximum bisections of graphs without short even cycles
Lin, Jing
Zeng, Qinghou
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2021, 180
[3] Maximum bisections of graphs without cycles of length four and five
Wu, Shufei
Zhong, Yuanyuan
DISCRETE APPLIED MATHEMATICS, 2025, 360 : 209 - 220
[4] Maximum Bisections of Graphs with Girth at Least Six
Wu, Shufei
Xiong, Xiaobei
GRAPHS AND COMBINATORICS, 2024, 40 (06)
[5] On bisections of graphs without complete bipartite graphs
Hou, Jianfeng
Wu, Shufei
JOURNAL OF GRAPH THEORY, 2021, 98 (04) : 630 - 641
[6] Bisections of Graphs Without Short Cycles
Fan, Genghua
Hou, Jianfeng
Yu, Xingxing
COMBINATORICS PROBABILITY & COMPUTING, 2018, 27 (01) : 44 - 59
[7] Bisections of graphs without K2,l
Jin, Jing
Xu, Baogang
DISCRETE APPLIED MATHEMATICS, 2019, 259 : 112 - 118
[8] Optimal bisections of directed graphs
Liu, Guanwu
Ma, Jie
Zu, Chunlei
RANDOM STRUCTURES & ALGORITHMS, 2024, 64 (01) : 138 - 153
[9] A note on bisections of graphs with girth at least 6
Lin, Jing
ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2019, (42): : 80 - 87
[10] A NOTE ON JUDICIOUS BISECTIONS OF GRAPHS
Wu, Shufei
Xiong, Xiaobei
BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2024, 110 (03) : 401 - 408

← 1 2 3 →