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

arXiv2204.06284MaRDI QIDQ6396405FDOQ6396405

Authors: Di Wu, Baogang Xu, Yian Xu 

Publication date: 13 April 2022

Abstract: A hole is an induced cycle of length at least 4. Let $lge2$ be a positive integer, let ${calG}_l$ denote the family of graphs which have girth $2l+1$ and have no holes of odd length at least $2l+3$, and let $Gin{calG}_l$. For a vertex $uinV(G)$ and a nonempty set $SsubseteqV(G)$, let $d(u,S)=mind(u,v):vinS$, and let $L_i(S)=uinV(G)mboxandd(u,S)=i$ for any integer $ige0$. We show that if $G[S]$ is connected and $G[L_i(S)]$ is bipartite for each $iin1,ldots,lfloorlover2floor$, then $G[L_i(S)]$ is bipartite for each $i>0$, and consequently $chi(G)le4$, where $G[S]$ denotes the subgraph induced by $S$. Let $het{a}^{-}$ be the graph obtained from the Petersen graph by deleting three vertices which induce a path, let $het{a}^{+}$ be the graph obtained from the Petersen graph by deleting two adjacent vertices, and let $heta$ be the graph obtained from $het{a}^{+}$ by removing an edge incident with two vertices of degree 3. For a graph $Gin{calG}_2$, we show that if $G$ is 3-connected and has no unstable 3-cutset then $G$ must induce either $heta$ or $het{a}^{-}$ but does not induce $het{a}^{+}$. As corollaries, $chi(G)le3$ for every graph $G$ of ${calG}_2$ that induces neither $heta$ nor $het{a}^{-}$, and minimal non-3-colorable graphs of ${calG}_2$ induce no $het{a}^{+}$.

This page was built for publication: On coloring of graphs of girth 2l + 1 without longer odd holes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6396405)