On coloring of graphs of girth 2l + 1 without longer odd holes

preprint2022arXivOpen access

Abstract

A hole is an induced cycle of length at least 4. Let ł≥2ł\ge 2 be a positive integer, let Gl{\cal G}_l denote the family of graphs which have girth 2ł+12ł+1 and have no holes of odd length at least 2ł+32ł+3, and let G∈GłG\in {\cal G}_ł. For a vertex u∈V(G)u\in V(G) and a nonempty set S⊆V(G)S\subseteq V(G), let d(u,S)=min⁡{d(u,v):v∈S}d(u, S)=\min\{d(u, v):v\in S\}, and let $L_i(S)=\{u\in V(G) \mbox{ and } d(u, S)=i\}$ for any integer i≥0i\ge 0. We show that if G[S]G[S] is connected and G[Li(S)]G[L_i(S)] is bipartite for each i∈{1,…,⌊ł2⌋}i\in\{1, \ldots, \lfloor{ł\over 2}\rfloor\}, then G[Li(S)]G[L_i(S)] is bipartite for each i>0i>0, and consequently χ(G)≤4χ(G)\le 4, where G[S]G[S] denotes the subgraph induced by SS. 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∈G2G\in{\cal G}_2, we show that if GG is 3-connected and has no unstable 3-cutset then GG must induce either θθ or θ−θ^- but does not induce θ+θ^+. As corollaries, χ(G)≤3χ(G)\le 3 for every graph GG of G2{\cal G}_2 that induces neither θθ nor θ−θ^-, and minimal non-3-colorable graphs of G2{\cal G}_2 induce no θ+θ^+.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.