Cycle Adjacency of Planar Graphs and 3-Colourability
Autor: | Xuding Zhu, Chung-Ying Yang |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2011 |
Předmět: | |
Zdroj: | Taiwanese J. Math. 15, no. 4 (2011), 1575-1580 |
Popis: | Suppose $G$ is a planar graph. Let $H_G$ be the graph with vertex set $V(H_G)=\{ C:C$ is a cycle of G with $|C|\in \{4,6,7\} \}$ and $E(H_G)=\{ C_iC_j: C_i$ and $C_j$ are adjacent in $G\}$. We prove that if any $3$-cycles and $5$-cycles are not adjacent to $i$-cycles for $3 \leq i \leq 7$, and $H_G$ is a forest, then $G$ is $3$-colourable. |
Databáze: | OpenAIRE |
Externí odkaz: |