Edge-colouring and total-colouring chordless graphs
From MaRDI portal
Publication:389214
DOI10.1016/j.disc.2013.03.020zbMath1408.05063arXiv1309.1842MaRDI QIDQ389214
Nicolas Trotignon, Celina M. Herrera de Figueiredo, Raphael C. S. Machado
Publication date: 20 January 2014
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1309.1842
68W40: Analysis of algorithms
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Characterizing k-chordal unichord-free graphs, Acyclic chromatic index of chordless graphs, Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs, Two complexity results for the vertex coloring problem, Strongly unichord-free graphs, Graph edge coloring: a survey, Classifying \(k\)-edge colouring for \(H\)-free graphs, Using SPQR-trees to speed up recognition algorithms based on 2-cutsets, Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs, The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs, The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring, Complexity-separating graph classes for vertex, edge and total colouring, Wheel-free planar graphs, Complexity separating classes for edge-colouring and total-colouring
Uses Software
Cites Work
- Total-chromatic number and chromatic index of dually chordal graphs
- The total chromatic number of split-indifference graphs
- On graphs with no induced subdivision of \(K_4\)
- Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
- Total chromatic number of unichord-free graphs
- Total 4-choosability of series-parallel graphs
- Edge and total choosability of near-outerplanar graphs
- Determining the total colouring number is NP-hard
- Decompositions for edge-coloring join graphs and cobipartite graphs
- NP-completeness of edge-colouring some restricted graphs
- Total colouring regular bipartite graphs is NP-hard
- List edge and list total colourings of multigraphs
- Characterizing and edge-colouring split-indifference graphs
- Decompositions for the edge colouring of reduced indifference graphs.
- Planar graphs of maximum degree seven are Class I
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Total colourings of graphs
- Chromatic index of graphs with no cycle with a unique chord
- Edge-colouring of join graphs
- The determination of the total chromatic number of series-parallel graphs with \((G) \geq 4\)
- Total chromatic number of one kind of join graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Total chromatic number of planar graphs with maximum degree ten
- The NP-completeness column: an ongoing guide
- The NP-Completeness of Edge-Coloring
- NP completeness of finding the chromatic index of regular graphs
- Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- Minimally 2-connected graphs.
- On Minimal Blocks
- Edge and total coloring of interval graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
