A coloring algorithm for \(4 K_1\)-free line graphs
From MaRDI portal
Publication:1686052
DOI10.1016/j.dam.2017.06.006zbMath1376.05054OpenAlexW2962698493MaRDI QIDQ1686052
Angèle M. Hamel, Frédéric Maffray, Dallas J. Fraser, Chính T. Hoàng
Publication date: 20 December 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2017.06.006
Related Items
Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs, On coloring a class of claw-free graphs., On the structure of graphs without claw, \(4K_1\) and co-R, On coloring a class of claw-free and hole-twin-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex coloring of graphs with few obstructions
- Some new hereditary classes where graph coloring remains NP-hard
- On the chromatic index of multigraphs without large triangles
- Topics on perfect graphs
- The strong perfect graph theorem
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Decomposition by clique separators
- Recognizing claw-free perfect graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- Some simplified NP-complete graph problems
- Linear recognition of pseudo-split graphs
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Handle-rewriting hypergraph grammars
- Clique-width for 4-vertex forbidden subgraphs
- Recognizing Berge graphs
- The NP-Completeness of Edge-Coloring
- How To Color Claw-Free Perfect Graphs
- Reducibility among Combinatorial Problems
- Characterizations of derived graphs
