2022/04/13 by Di Wu, Wu, Di, Baogang Xu +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2204.06284
openalex publication_date 2022/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A hole is an induced cycle of length at least 4. Let ł≥ 2 be a positive integer, let \cal Gl denote the family of graphs which have girth 2ł+1 and have no holes of odd length at least 2ł+3, and let G∈ \cal G_ł. For a vertex u∈ V(G) and a nonempty set S⊆ V(G), let d(u, S)=min\d(u, v):v∈ S\, and let Li(S)=\u∈ V(G) and d(u, S)=i\ for any integer i≥ 0. We show that if G[S] is connected and G[Li(S)] is bipartite for each i∈\1, …, \lfloorł\over 2\rfloor\, then G[Li(S)] is bipartite for each i>0, and consequently χ(G)≤ 4, where G[S] denotes the subgraph induced by S. Let θ- be the graph obtained from the Petersen graph by deleting three vertices which induce a path, let θ+ be the graph obtained from the Petersen graph by deleting two adjacent vertices, and let θ be the graph obtained from θ+ by removing an edge incident with two vertices of degree 3. For a graph G∈\cal G2, we show that if G is 3-connected and has no unstable 3-cutset then G must induce either θ or θ- but does not induce θ+. As corollaries, χ(G)≤ 3 for every graph G of \cal G2 that induces neither θ nor θ-, and minimal non-3-colorable graphs of \cal G2 induce no θ+.