Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds

作     者：Couturier, Jean-Francois Golovach, Petr A. Kratsch, Dieter Liedloff, Mathieu Pyatkin, Artem 

作者机构：Univ Paul Verlaine Metz Lab Informat Theor & Appl F-57045 Metz 01 France Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2013年第52卷第4期

页      面：645-667页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：ANR under project AGAPE [ANR-09-BLAN-0159-03] EPSRC [EP/G043434/1, EP/F064551/1] RFBR [12-01-00184-a, 12-01-00093-a] Ministry of education and science of the Russian Federation [14.740.11.0868] EPSRC [EP/F064551/1, EP/G043434/1] Funding Source: UKRI 

主　　题：Algorithms Graphs Exact exponential time algorithms Enumeration Counting Coloring 

摘      要：Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree. This paper studies enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings of graphs. One part deals with the enumeration of all edge 3-colorings, all total 4-colorings and all L(2,1)-labelings of span 5 of a given connected cubic graph. Branching algorithms to solve these enumeration problems are established. They imply upper bounds on the maximum number of edge 3-colorings, total 4-colorings and L(2,1)-labelings of span 5 in any n-vertex connected cubic graphs. Corresponding combinatorial lower bounds are also provided. The other part of the paper studies dynamic programming algorithms solving counting problems. On one hand, algorithms to count the number of edge k-colorings and total k-colorings for graphs of bounded pathwidth are given. On the other hand, an algorithm to count the number of L(2,1)-labelings of span 4 for graphs of maximum degree three are given.