论文标题
关于围墙2L + 1的图形，没有更长的奇数孔
On coloring of graphs of girth 2l + 1 without longer odd holes
论文作者
论文摘要
一个孔是一个至少4的诱发周期。让$ ol \ ge 2 $成为一个正整数，让$ {\ cal g} _l $表示图形的家族，这些图形含有$ 2V+1 $，没有奇数长度$ 2万+3 $的孔，然后让$ g \ in {\ cal g} _ $ g} _ $ g} _ $。对于v（g）$中的顶点$ u \，$ s \ subseteq v（g）$，让$ d（u，s）= \ min \ {d（u，v）：v \ in s \} $，和让$ l_i（s）= \ r_i（s）= \ \ in v in（g）u \ in（g） $ i \ ge 0 $。我们表明，如果连接了$ g [s] $，并且$ g [l_i（s）] $是\ {1，\ ldots in \ {1，\ lfloor {f \ for 2} \ rfloor \ rfloor \} $的双分式，则每个$ g [l_i（s） $ g [s] $表示$ s $引起的子图。令$θ^ - $是通过删除诱导路径的三个顶点获得的图表，让$θ^+$是通过删除两个相邻的顶点获得的图表，让$θ$是从$θ^+$中获得$θ^+$的图形，通过将$θ^+获得的$θ^$删除$ g的$ g g。表明，如果$ g $是3点连接并且没有不稳定的3切口，那么$ g $必须诱导$θ$或$θ^ - $，但不会引起$θ^+$。作为推论，每张图$ g $ of $ {\ cal g} _2 $均未诱导$θ$也不$θ^ - $，而最小的非3个性图的$ {\ cal g} _2 _2 _2 $ indue no $θ^+$。
A hole is an induced cycle of length at least 4. Let $ł\ge 2$ be a positive integer, let ${\cal G}_l$ denote the family of graphs which have girth $2ł+1$ and have no holes of odd length at least $2ł+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{ł\over 2}\rfloor\}$, then $G[L_i(S)]$ is bipartite for each $i>0$, and consequently $χ(G)\le 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\in{\cal G}_2$, 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)\le 3$ for every graph $G$ of ${\cal G}_2$ that induces neither $θ$ nor $θ^-$, and minimal non-3-colorable graphs of ${\cal G}_2$ induce no $θ^+$.
