講演抄録/キーワード |
講演名 |
2013-03-18 14:10
C7-彩色可能な平面グラフにおける内周の下界値に関する考察 ○浅野竜男・上嶋章宏(阪電通大) COMP2012-57 |
抄録 |
(和) |
本稿では,$n/k$-彩色問題($n, k$は$n/k \geq 2$を満たす自然数)の部分問題である$C_{2k+1}$-彩色問題
($C_{2k+1}$は頂点数$2k+1$の奇数長閉路)について考える.内周$(20k-2)/3$以上の平面グラフの$C_{2k+1}$-彩色
可能性が示されており,$C_5$-彩色可能な平面グラフの内周の下界はさらに改善されている.
本稿では,内周4以上でかつ最大平均次数$\frac{20}{9}$未満である平面グラフの$C_7$-彩色可能性を示す. |
(英) |
This report considers the $C_{2k+1}$-coloring problem, which is a subproblem for the $n/k$-coloring problem,
where $n, k$ are positive integers with $n/k \geq 2$. It has already shown that every planar graph with girth
at least $(20k-2)/3$ has a $C_{2k+1}$-coloring, and the bound for $C_5$-colorability was improved.
In this report, we prove that every triangle-free graph whose all subgraphs have average degree less than
$\frac{20}{9}$ is $C_7$-colorable. |
キーワード |
(和) |
$n/k$-彩色 / $C_7$-彩色 / Circular Coloring / 平面グラフ / 内周 / / / |
(英) |
$n/k$-Coloring / $C_7$-Coloring / Circular Coloring / Planar Graphs / Girths / / / |
文献情報 |
信学技報, vol. 112, no. 498, COMP2012-57, pp. 31-38, 2013年3月. |
資料番号 |
COMP2012-57 |
発行日 |
2013-03-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-57 |