Graphs with girth 2 ℓ 1 and without longer odd holes that contain an odd K4-subdivision Rong Chen Yidong Zhou
2025-05-06
1
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
1
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 finite, 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 Classification: 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).
1
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 first 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.
2
摘要：
展开>>
收起<<
Graphswithgirth2ℓ+1andwithoutlongeroddholesthatcontainanoddK4-subdivisionRongChen,YidongZhouCenterforDiscreteMathematics,FuzhouUniversityFuzhou,P.R.ChinaJanuary3,20241AbstractWesaythatagraphGhasanoddK4-subdivisionifsomesubgraphofGisisomorphictoaK4-subdivisionwhichifembeddedintheplanetheboundaryofeac...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
分类：图书资源
价格：10玖币
属性：10 页
大小：338.97KB
格式：PDF
时间：2025-05-06
渝公网安备50010702506394
