Clique-coloring of K₃,3-minor free graphs

DOI10.1007/S41980-019-00341-0MaRDI QIDQ826557zbMATH OpenOpenAlexFDO

Authors Behnaz Omoomi, Maryam Taleb

Publication date 5 January 2021

Published in Bulletin of the Iranian Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

\(K_{3,3}\)-minorclaw-free graphsclique chromatic numberclique-coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: A clique-coloring of a given graph $G$ is a coloring of the vertices of $G$ such that no maximal clique of size at least two is monocolored. The clique-chromatic number of $G$ is the least number of colors for which $G$ admits a clique-coloring. It has been proved that every planar graph is $3$-clique colorable and every claw-free planar graph, different from an odd cycle, is $2$-clique colorable. In this paper, we generalize these results to $K_{3,3}$-minor free ($K_{3,3}$-subdivision free) graphs.

Recommendations

• Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)
• A linear-time algorithm for clique-coloring planar graphs
• Clique-transversal sets and clique-coloring in planar graphs
• Clique-chromatic numbers of claw-free graphs
• Coloring the Maximal Cliques of Graphs

Cites work

• Characterizations of derived graphs
• Claw-free graphs. IV: Decomposition theorem
• Clique-chromatic numbers of claw-free graphs
• Clique-coloring claw-free graphs
• 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 clique-hypergraphs of graphs with no subdivision of \(K_5\)
• Coloring the Maximal Cliques of Graphs
• Complexity of clique-coloring odd-hole-free graphs
• Graph theory
• scientific article; zbMATH DE number 1342090 (Why is no real title available?)
• On the complexity of bicoloring clique hypergraphs of graphs
• Sur le coloriage des graphs
• The Grötzsch theorem for the hypergraph of maximal cliques
• Two-colouring all two-element maximal antichains
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(5)

• A linear-time algorithm for clique-coloring planar graphs
• Clique-coloring numbers of some product graphs
• Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)
• scientific article; zbMATH DE number 2192097 (Why is no real title available?)
• Clustered 3-colouring graphs of bounded degree

This page was built for publication: Clique-coloring of \(K_{3,3}\)-minor free graphs

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