Complexity-separating graph classes for vertex, edge and total colouring

DOI10.1016/j.dam.2019.02.039zbMath1440.05188OpenAlexW2924127518MaRDI QIDQ2184678

Celina M. Herrera de Figueiredo

Publication date: 29 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.02.039

zbMATH Keywords

analysis of algorithmsgraph algorithmsproblem complexitystructural characterization of types of graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The overfull conjecture on split-comparability and split-interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Total-chromatic number and chromatic index of dually chordal graphs
• Edge-colouring and total-colouring chordless graphs
• The total chromatic number of split-indifference graphs
• Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
• The complexity of SIMPLE MAX-CUT on comparability graphs
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• Complexity of clique coloring and related problems
• Total chromatic number of unichord-free graphs
• A total-chromatic number analogue of Plantholt's theorem
• The strong perfect graph theorem
• Perfect graphs of arbitrarily large clique-chromatic number
• Determining the total colouring number is NP-hard
• Decompositions for edge-coloring join graphs and cobipartite graphs
• Steiner problem in Halin networks
• Hamiltonian circuits in interval graph generalizations
• NP-completeness of edge-colouring some restricted graphs
• Two-colouring all two-element maximal antichains
• The complexity of domination problems in circle graphs
• Maximum cut on line and total graphs
• Total colouring regular bipartite graphs is NP-hard
• Characterizing and edge-colouring split-indifference graphs
• On edge-colouring indifference graphs
• Efficient graph representations
• How to find overfull subgraphs in graphs with large maximum degree. II
• Coloring square-free Berge graphs
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Planar graphs of maximum degree seven are Class I
• Algorithmic graph theory and perfect graphs
• Total colourings of graphs
• HAMILTONian circuits in chordal bipartite graphs
• Chromatic index of graphs with no cycle with a unique chord
• Edge-colouring of join graphs
• Complexity separating classes for edge-colouring and total-colouring
• Recognizing Berge graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• The world of hereditary graph classes viewed through Truemper configurations
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
• The NP-completeness column: an ongoing guide
• The chromatic index of graphs with a spanning star
• The NP-Completeness of Edge-Coloring
• The chromatic index of complete multipartite graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Coloring the Maximal Cliques of Graphs
• NP completeness of finding the chromatic index of regular graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Reducibility among Combinatorial Problems
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Clique Cover on Sparse Networks
• Decomposing and Clique‐Coloring (Diamond, Odd‐Hole)‐Free Graphs
• The Star and Biclique Coloring and Choosability Problems
• Every planar graph with maximum degree 7 is of class 1

This page was built for publication: Complexity-separating graph classes for vertex, edge and total colouring