Graphs with girth 2 ℓ 1 and without longer odd holes that contain an odd K4-subdivision Rong Chen Yidong Zhou

2025-05-06 0 0 338.97KB 10 页 10玖币

侵权投诉

Graphs with girth 2ℓ+ 1 and without longer odd holes that

contain an odd K4-subdivision

Rong Chen, Yidong Zhou

Center for Discrete Mathematics, Fuzhou University

Fuzhou, P. R. China

January 3, 2024

Abstract

We say that a graph Ghas an odd K4-subdivision if some subgraph of Gis isomorphic

to a K4-subdivision which if embedded in the plane the boundary of each of its faces

has odd length and is an induced cycle of G. For a number ℓ≥2, let Gℓdenote the

family of graphs which have girth 2ℓ+ 1 and have no odd hole with length greater than

2ℓ+ 1. Wu, Xu and Xu conjectured that every graph in Sℓ≥2Gℓis 3-colorable. Recently,

Chudnovsky et al. and Wu et al., respectively, proved that every graph in G2and G3is

3-colorable. In this paper, we prove that no 4-vertex-critical graph in Sℓ≥5Gℓhas an odd

K4-subdivision. Using this result, Chen proved that all graphs in Sℓ≥5Gℓare 3-colorable.

Key Words: chromatic number; odd holes.

1 Introduction

All graphs considered in this paper are ﬁnite, simple, and undirected. A proper coloring of

a graph Gis an assignment of colors to the vertices of Gsuch that no two adjacent vertices

receive the same color. A graph is k-colorable if it has a proper coloring using at most k

colors. The chromatic number of G, denoted by χ(G), is the minimum number ksuch that

Gis k-colorable.

The girth of a graph G, denoted by g(G), is the minimum length of cycles in G. A hole

in a graph is an induced cycle of length at least four. An odd hole means a hole of odd

length. For any integer ℓ≥2, let Gℓbe the family of graphs that have girth 2ℓ+ 1 and

have no odd holes of length at least 2ℓ+ 3. Robertson conjectured in [4] that the Petersen

1Mathematics Subject Classiﬁcation: 05C15, 05C17, 05C69.

Emails: rongchen13@163.com (R. Chen), zoed98@126.com (Y. Zhou).

This research was partially supported by grants from the National Natural Sciences Foundation of China

(No. 11971111).

arXiv:2210.12376v4 [math.CO] 30 Dec 2023

graph is the only graph in G2that is 3-connected and internally 4-connected. Plummer and

Zha [5] disproved Robertson’s conjecture and proposed the conjecture that all 3-connected

and internally 4-connected graphs in G2have bounded chromatic numbers, and proposed the

strong conjecture that such graphs are 3-colorable. The ﬁrst was proved by Xu, Yu, and

Zha [9], who proved that all graphs in G2are 4-colorable. The strong conjecture proposed by

Plummer and Zha in [5] was solved by Chudnovsky and Seymour [2]. Wu, Xu, and Xu [7]

showed that graphs in Sℓ≥2Gℓare 4-colorable and conjectured

Conjecture 1.1. ([7], Conjecture 6.1.) For each integer ℓ≥2, every graph in Gℓis 3-

colorable.

Wu, Xu and Xu [8] recently proved that Conjecture 1.1 holds for ℓ= 3.

We say that a graph Ghas an odd K4-subdivision if some subgraph of Gis isomorphic

to a K4-subdivision which if embedded in the plane the boundary of each of its faces has

odd length and is an induced cycle of G. Note that an odd K4-subdivision of Gmaybe not

induced. However, when G∈ Gℓfor each integer ℓ≥2, all odd K4-subdivisions of Gare

induced by Lemma 2.6 (2). In this paper, we prove the following theorem.

Theorem 1.2. No 4-vertex-critical graph in Sℓ≥5Gℓhas an odd K4-subdivision.

Using Theorem 1.2, Chen [1] proved that Conjecture 1.1 holds for all ℓ≥5. Recently,

following idea in this paper and [1], Wang and Wu [6] further proved that Conjecture 1.1

holds for ℓ= 4.

2 Preliminaries

Acycle is a connected 2-regular graph. Let Gbe a graph. A vertex v∈V(G) is called a degree-

kvertex if it has exactly k neighbours. For any U⊆V(G), let G[U] be the subgraph of G

induced on U. For subgraphs Hand H′of G, set |H|:= |E(H)|and H∆H′:= E(H)∆E(H′).

Let H∪H′denote the subgraph of Gwhose vertex set is V(H)∪V(H′) and edge set is

E(H)∪E(H′). Let H∩H′denote the subgraph of Gwith edge set E(H)∩E(H′) and

without isolated vertex. Let N(H) be the set of vertices in V(G)−V(H) that have a

neighbour in H. Set N[H] := N(H)∪V(H).

Let Pbe an (x, y)-path and Qbe a (y, z)-path. When Pand Qare internally disjoint,

let P Q denote the (x, z)-path P∪Q. Evidently, P Q is a path when x̸=z, and P Q is a cycle

when x=z. Let P∗denote the set of internal vertices of P. When u, v ∈V(P), let P(u, v)

denote the subpath of Pwith ends u, v. For simplicity, we will let P∗(u, v) denote (P(u, v))∗.

A graph is k-vertex-critical if χ(G) = kbut χ(G\v)< k for each v∈V(G). Dirac in [3]

proved that every k-vertex-critical graph is (k−1)-edge-connected. Hence, we have

Lemma 2.1. For each integer k≥4, each k-vertex-critical graph Ghas no 2-edge-cut.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Graphswithgirth2ℓ+1andwithoutlongeroddholesthatcontainanoddK4-subdivisionRongChen,YidongZhouCenterforDiscreteMathematics,FuzhouUniversityFuzhou,P.R.ChinaJanuary3,20241AbstractWesaythatagraphGhasanoddK4-subdivisionifsomesubgraphofGisisomorphictoaK4-subdivisionwhichifembeddedintheplanetheboundaryofeac...

展开>> 收起<<

Graphs with girth 2 ℓ 1 and without longer odd holes that contain an odd K4-subdivision Rong Chen Yidong Zhou.pdf

共10页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Graphs with girth 2 ℓ 1 and without longer odd holes that contain an odd K4-subdivision Rong Chen Yidong Zhou

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: