structural graph theory and eifficient algorithm for graph coloring problems

结构图论和图着色问题的高效算法

• 批准号: 21684002
• 负责人: KAWARABAYASHI Ken-ichi
• 金额: $ 6.82万
• 依托单位: National Institute of Informatics
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (A)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009-04-01 至 2013-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21684002/
• 关键词: グラフ彩色; アルゴリズム; Hadwiger予想; グラフ; 平面グラフ; グラフマイナー; グラフ細分; 多項式時間; 曲面上のグラフ; 4色定理; 選択数; 独立点集合

In this research, we have worked on graph coloring problem for1. graphs on a surface, and 2. minor-closed family of graphs.Concerning the first one, we give several algorithmic results. Namely. we give a polynomial time algorithm for deciding 5-list-colorability of graphs on a fixed surface, and for deciding 3-list-colorablity of graphs of girth five on a fixed surface. Concerning the second one, we show that minimal-counterexample to the famous Hadwiger's conjecture is 0.2k-connected for the case k. This is the first step toward a chacterization of such a minimal-counterexample.

在本研究中，我们研究了图的着色问题。图在一个表面上，和2。关于第一类图，我们给出了几个算法结果。也就是说本文给出了判定固定曲面上图的5-列表可染性和判定固定曲面上围长为5的图的3-列表可染性的多项式时间算法。对于第二个猜想，我们证明了著名的Hadwiger猜想的极小反例在k情形下是0.2k-连通的。这是对这样一个极小反例进行特征化的第一步。

项目成果

An O(\log n)-approximation algorithm for the disjoint paths problem in

求解不相交路径问题的 O(log n) 近似算法

• 发表时间: 2013
• 期刊: ACM transaction on Algorithms
• 作者: Ken-ichi Kawarabayashi;Yusuke Kobayashi
• 通讯作者: Yusuke Kobayashi

Decomposition, approximation, and coloring of odd-minor-free graphs

无奇次子图的分解、近似和着色

• 发表时间: 2010
• 期刊: ACM-SIAM Symposium on Discrete Algorithms, (SODA'10)
• 作者: E.Demaine et al.

N-flips in even triangulations on a surface

曲面上均匀三角剖分中的 N 翻转

• 发表时间: 2009
• 期刊: J.Combin.Theory Ser.B 99
• 作者: Omura;K.;& Okada;N.;K.Kawarabayashi et al.
• 通讯作者: K.Kawarabayashi et al.

Graphs without subdivision

没有细分的图

• 发表时间: 2009
• 作者: Saki Tanaka;Jiro Murata 他;K. Kawarabayashi
• 通讯作者: K. Kawarabayashi

The disjoint paths problem in quadratic time

• DOI: 10.1016/j.jctb.2011.07.004
• 发表时间: 2012-03-01
• 期刊: JOURNAL OF COMBINATORIAL THEORY SERIES B
• 影响因子: 1.4
• 作者: Kawarabayashi, Ken-ichi;Kobayashi, Yusuke;Reed, Bruce
• 通讯作者: Reed, Bruce