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

• Published in: arXiv.org 2022-04
• Main Authors: Wu, Di, Xu, Baogang, Xu, Yian
• Format: Article
• Language: English
• Subjects: Apexes; Graph theory; Graphs; Integers
• ISSN: 2331-8422

A hole is an induced cycle of length at least 4. Let \(\l\ge 2\) be a positive integer, let \({\cal G}_l\) denote the family of graphs which have girth \(2\l+1\) and have no holes of odd length at least \(2\l+3\), and let \(G\in {\cal G}_ł\). For a vertex \(u\in V(G)\) and a nonempty set \(S\subseteq V(G)\), let \(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\ge 0\). We show that if \(G[S]\) is connected and \(G[L_i(S)]\) is bipartite for each \(i\in\{1, \ldots, \lfloor{\l\over 2}\rfloor\}\), then \(G[L_i(S)]\) is bipartite for each \(i>0\), and consequently \(\chi(G)\le 4\), where \(G[S]\) denotes the subgraph induced by \(S\). Let \(\theta^-\) be the graph obtained from the Petersen graph by deleting three vertices which induce a path, let \(\theta^+\) be the graph obtained from the Petersen graph by deleting two adjacent vertices, and let \(\theta\) be the graph obtained from \(\theta^+\) by removing an edge incident with two vertices of degree 3. For a graph \(G\in{\cal G}_2\), we show that if \(G\) is 3-connected and has no unstable 3-cutset then \(G\) must induce either \(\theta\) or \(\theta^-\) but does not induce \(\theta^+\). As corollaries, \(\chi(G)\le 3\) for every graph \(G\) of \({\cal G}_2\) that induces neither \(\theta\) nor \(\theta^-\), and minimal non-3-colorable graphs of \({\cal G}_2\) induce no \(\theta^+\).