Colorings with few colors: counting, enumeration and combinatorial bounds
From MaRDI portal
Publication:2392249
DOI10.1007/s00224-012-9410-7zbMath1269.05034MaRDI QIDQ2392249
Dieter Kratsch, Mathieu Liedloff, Artem V. Pyatkin, Jean-François Couturier, 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
05C30: Enumeration in graph theory
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Narrow sieves for parameterized paths and packings, Solving Matching Problems Efficiently in Bipartite Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact exponential algorithms.
- Exact algorithms for \(L(2,1)\)-labeling of graphs
- Improved edge-coloring with three colors
- Determining the total colouring number is NP-hard
- The maximum number of perfect matchings in graphs with a given degree sequence
- On two techniques of combining branching and treewidth
- Pathwidth of cubic graphs and exact algorithms
- Treewidth. Computations and approximations
- On the number of 3-edge colorings of cubic graphs
- Perfect matchings in \(\varepsilon\)-regular graphs
- An exact algorithm for the channel assignment problem
- On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs
- Enumerating the edge-colourings and total colourings of a regular graph
- On independent sets and bicliques in graphs
- On the total coloring of certain graphs
- On Improved Exact Algorithms for L(2,1)-Labeling of Graphs
- Fast Exact Algorithm for L(2,1)-Labeling of Graphs
- Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- 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