COLORING ALGORITHMS ON SUBCUBIC GRAPHS
From MaRDI portal
Publication:5696963
DOI10.1142/S0129054104002285zbMath1101.68735MaRDI QIDQ5696963
San Skulrattanakulchai, Harold N. Gabow
Publication date: 19 October 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Related Items
\(\Delta \)-list vertex coloring in linear time ⋮ Multigraphs with \(\Delta \geq 3\) are totally-\((2\Delta - 1)\)-choosable
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Determining the total colouring number is NP-hard
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- List-colourings of graphs
- On graphs critical with respect to edge-colourings
- Three short proofs in graph theory
- Edge-choosability in line-perfect multigraphs
- Edge-choosability of multicircuits
- Total colouring regular bipartite graphs is NP-hard
- List edge and list total colourings of multigraphs
- Some APX-completeness results for cubic graphs
- On list edge-colorings of subcubic graphs
- 4-edge-coloring graphs of maximum degree 3 in linear time
- The list chromatic index of a bipartite multigraph
- On the total coloring of certain graphs
- List edge colourings of some 1-factorable multigraphs
- Efficient Algorithms for Petersen's Matching Theorem
- Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests
- Δ-List Vertex Coloring in Linear Time
- An Efficient Parallel Biconnectivity Algorithm
- A note on list-colorings
- The NP-Completeness of Edge-Coloring
- List Total Colourings of Graphs
- Total choosability of multicircuits I
- Total choosability of multicircuits II
- On Total Chromatic Number of a Graph
