Presentation	2013/3/11 A Note on Lower Bounds of the Girth of Planar C_7-Colorable Graphs Tatsuo ASANO, Akihiro UEJIMA,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	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≧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 20/9 is C_7-colorable.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	n/k-Coloring / C_7-Coloring / Circular Coloring / Planar Graphs / Girths
Paper #	C0MP2012-57
Date of Issue

Conference Information
Committee	COMP
Conference Date	2013/3/11(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	A Note on Lower Bounds of the Girth of Planar C_7-Colorable Graphs
Sub Title (in English)
Keyword(1)	n/k-Coloring
Keyword(2)	C_7-Coloring
Keyword(3)	Circular Coloring
Keyword(4)	Planar Graphs
Keyword(5)	Girths
1st Author's Name	Tatsuo ASANO
1st Author's Affiliation	School of Engineering, Osaka Electro-Communication University()
2nd Author's Name	Akihiro UEJIMA
2nd Author's Affiliation	School of Engineering, Osaka Electro-Communication University
Date	2013/3/11
Paper #	C0MP2012-57
Volume (vol)	vol.112
Number (no)	498
Page	pp.pp.-
#Pages	8
Date of Issue