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