Graph Subcolorings: Complexity and Algorithms

DOI10.1137/S0895480101395245zbMath1029.05052OpenAlexW1978588354WikidataQ56428503 ScholiaQ56428503MaRDI QIDQ4443116

Jiří Fiala, Van Bang Le, Eike Seidel, Klaus Jansen

Publication date: 8 January 2004

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480101395245

zbMATH Keywords

computational complexitytreewidthcographcliquewidthgraph subcoloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

Trees, paths, stars, caterpillars and spiders ⋮ Dynamic \(F\)-free coloring of graphs ⋮ Trees, Paths, Stars, Caterpillars and Spiders ⋮ 2-subcoloring is NP-complete for planar comparability graphs ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Unnamed Item ⋮ Path-bicolorable graphs ⋮ On the algorithmic aspects of strong subcoloring ⋮ A hypocoloring model for batch scheduling ⋮ Near-colorings: non-colorable graphs and NP-completeness ⋮ SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ On star and caterpillar arboricity ⋮ Path-Bicolorable Graphs ⋮ On some arboricities in planar graphs

This page was built for publication: Graph Subcolorings: Complexity and Algorithms