Colorings with few colors: counting, enumeration and combinatorial bounds

DOI10.1007/S00224-012-9410-7MaRDI QIDQ2392249zbMATH OpenOpenAlexFDO

Authors Jean-François Couturier, Dieter Kratsch, Mathieu Liedloff, Artem Pyatkin, Petr A. Golovach

Publication date 1 August 2013

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-012-9410-7

zbMATH Keywords

coloringcountingenumerationexact exponential time algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Colorings with few colors: counting, enumeration and combinatorial bounds
• Enumerating the edge-colourings and total colourings of a regular graph
• Exact algorithms for counting 3-colorings of graphs
• scientific article; zbMATH DE number 2089961
• The complexity of counting edge colorings for simple graphs

Cites work

• 3-coloring in time
• An exact algorithm for the channel assignment problem
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Combinatorial bounds via measure and conquer
• Determining the total colouring number is NP-hard
• Edge-Coloring Partialk-Trees
• Enumerating the edge-colourings and total colourings of a regular graph
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Exact exponential algorithms.
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• scientific article; zbMATH DE number 5605070 (Why is no real title available?)
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Improved edge-coloring with three colors
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• On cliques in graphs
• On improved exact algorithms for \(L(2,1)\)-labeling of graphs
• On independent sets and bicliques in graphs
• On the complexity of exact algorithm for L(2,1)-labeling of graphs
• On the number of 3-edge colorings of cubic graphs
• On the total coloring of certain graphs
• On two techniques of combining branching and treewidth
• Pathwidth of cubic graphs and exact algorithms
• Perfect matchings in \(\varepsilon\)-regular graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The maximum number of perfect matchings in graphs with a given degree sequence
• The NP-Completeness of Edge-Coloring
• Treewidth. Computations and approximations

Cited in

(6)

• Enumerating the edge-colourings and total colourings of a regular graph
• Coloring the \(n\)-smooth numbers with \(n\) colors
• Narrow sieves for parameterized paths and packings
• Solving matching problems efficiently in bipartite graphs
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Multicolor containers, extremal entropy, and counting

This page was built for publication: Colorings with few colors: counting, enumeration and combinatorial bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392249)