Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds

DOI10.1007/978-3-642-16926-7_6zbMath1309.05172OpenAlexW1579538307MaRDI QIDQ3057611

Dieter Kratsch, Jean-François Couturier, Petr A. Golovach

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Enumerating the edge-colourings and total colourings of a regular graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Evaluation of permanents in rings and semirings
• Improved edge-coloring with three colors
• Determining the total colouring number is NP-hard
• On two techniques of combining branching and treewidth
• Pathwidth of cubic graphs and exact algorithms
• An exact algorithm for the channel assignment problem
• On the total coloring of certain graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Exact Algorithms for L(2,1)-Labeling of Graphs
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• Edge-Coloring Partialk-Trees
• The NP-Completeness of Edge-Coloring
• 3-coloring in time
• Combinatorial bounds via measure and conquer
• On cliques in graphs
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds