Coloring clique-hypergraphs of graphs with no subdivision of K₅

DOI10.1016/J.TCS.2015.05.030zbMATH Open1331.05086OpenAlexW630596220MaRDI QIDQ500982FDOQ500982

Authors: Erfang Shan, Liying Kang 

Publication date: 8 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.05.030

Recommendations

• Clique-coloring of \(K_{3,3}\)-minor free graphs
• List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly
• A linear-time algorithm for clique-coloring planar graphs
• Clique-chromatic numbers of claw-free graphs
• Clique-transversal sets and clique-coloring in planar graphs

zbMATH Keywords

planar graphpolynomial-time algorithm\(K_5\)-subdivision-free graphclique-coloringclique-hypergraph

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Sur le coloriage des graphs
• Über eine Eigenschaft der ebenen Komplexe
• Title not available (Why is that?)
• Title not available (Why is that?)
• The four-colour theorem
• Complexity of clique coloring and related problems
• Covering the cliques of a graph with vertices
• Clique-transversal sets and clique-coloring in planar graphs
• Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
• Clique-transversal sets of line graphs and complements of line graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• The Grötzsch theorem for the hypergraph of maximal cliques
• Coloring the Maximal Cliques of Graphs
• Colouring clique-hypergraphs of circulant graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Complexity of clique-coloring odd-hole-free graphs
• Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
• Chains, antichains, and fibres
• Two-colouring all two-element maximal antichains
• Clique-coloring some classes of odd-hole-free graphs
• On the divisibility of graphs

Cited In (5)

• Clique-coloring of \(K_{3,3}\)-minor free graphs
• Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)
• A linear-time algorithm for clique-coloring planar graphs
• List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly
• K₅-Subdivisions in Graphs

This page was built for publication: Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q500982)