Clique coloring \(B_1\)-EPG graphs

DOI10.1016/j.disc.2017.01.019zbMath1357.05036arXiv1602.06723OpenAlexW2963963386MaRDI QIDQ512582

María Pía Mazzoleni, Flavia Bonomo-Braberman, Maya Jakobine Stein

Publication date: 27 February 2017

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

Full work available at URL: https://arxiv.org/abs/1602.06723

zbMATH Keywords

polynomial time algorithmedge intersection graphsclique coloringpaths on grids

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid ⋮ CPG graphs: some structural and hardness results ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid ⋮ A linear-time algorithm for clique-coloring planar graphs ⋮ List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly

Cites Work

• Unnamed Item
• Perfect graphs of arbitrarily large clique-chromatic number
• Two-colouring all two-element maximal antichains
• Fibres and ordered set coloring
• Edge-intersection graphs of grid paths: the bend-number
• Clique-Coloring Circular-Arc Graphs
• Approximation Algorithms for B 1-EPG Graphs
• Edge intersection graphs of single bend paths on a grid
• Clique-coloring UE and UEH graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Sur le coloriage des graphs
• Colouring clique-hypergraphs of circulant graphs

This page was built for publication: Clique coloring \(B_1\)-EPG graphs