Combinatorial Geometry and Graph Theory

DOI10.1007/b105263zbMath1117.05038OpenAlexW2480216131MaRDI QIDQ5491719

Hajo J. Broersma

Publication date: 10 October 2006

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b105263

zbMATH Keywords

computational complexitygraph coloringgraph partitioningplanar graphforbidden subgraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items

An \(O(n\log n)\) algorithm for finding edge span of cacti ⋮ On the hardness of computing span of subcubic graphs ⋮ Online \(L(2,1)\)-coloring problem on paths with restricted size of memory ⋮ The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones ⋮ The backbone coloring problem for bipartite backbones ⋮ The distant-2 chromatic number of random proximity and random geometric graphs ⋮ Optimal backbone coloring of split graphs with matching backbones ⋮ On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles ⋮ \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings ⋮ The computational complexity of the backbone coloring problem for planar graphs with connected backbones