Equitable clique-coloring in claw-free graphs with maximum degree at most 4

DOI10.1007/S00373-020-02253-XMaRDI QIDQ2657098zbMATH OpenOpenAlexFDO

Authors Zuosong Liang, Yanxia Dong, Yancai Zhao, Huiyu Xing

Publication date 17 March 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-020-02253-x

zbMATH Keywords

claw-free graphequitable clique-coloringlinear time algorithm

Mathematics Subject Classification ID

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

Review text

A clique of a graph \(G\) is a set of pairwise adjacent vertices of \(G\). A clique on \(m\) vertices is called an \(m\)-clique of \(G\). A clique-coloring, also known as weak coloring, is an assignment of colors to the vertices of \(G\) in such a way that no inclusion-wise maximal clique of size at least two is monochromatic. An equitable vertex-coloring of \(G\) is a proper vertex-coloring such that any two color classes differ in size by at most one. An equitable clique-coloring of \(G\) is a clique-coloring such that any two color classes differ in size by at most one. If \(G\) has an equitable clique-coloring with \(k\) colors, we say that \(G\) is equitably \(k\)-clique colorable. The purpose of the paper is to show that every connected claw-free graph with maximum degree at most four, other than an odd cycle greater than three, is also equitably 2-clique-colorable, where the claw is the complete bipartite graph \(K(1;3)\). The paper also gives an algorithm for an equitable 2-clique-coloring in linear time for this class of graphs.

Recommendations

• Clique-coloring claw-free graphs
• Equitable 4-coloring of cacti and edge-cacti in polynomial time
• Clique-chromatic numbers of claw-free graphs
• scientific article; zbMATH DE number 1302199
• Coloring the Maximal Cliques of Graphs

Cites work

• A fast algorithm for equitable coloring
• A linear-time algorithm for clique-coloring problem in circular-arc graphs
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Clique-coloring claw-free graphs
• Clique-coloring some classes of odd-hole-free graphs
• Clique-perfectness of claw-free planar graphs
• Clique-transversal sets and clique-coloring in planar graphs
• Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
• Coloring the cliques of line graphs
• Coloring the Maximal Cliques of Graphs
• Complexity of clique coloring and related problems
• Complexity of clique-coloring odd-hole-free graphs
• Decomposing and clique-coloring (diamond, odd-hole)-free graphs
• Equipartite colorings in graphs and hypergraphs
• Equitable coloring and the maximum degree
• Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• On the complexity of bicoloring clique hypergraphs of graphs
• Perfect graphs of arbitrarily large clique-chromatic number
• Perfect graphs with no balanced skew-partition are 2-clique-colorable
• Sur le coloriage des graphs
• The Grötzsch theorem for the hypergraph of maximal cliques

Cited in

(2)

• Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring
• On the complexity of local-equitable coloring in claw-free graphs with small degree

This page was built for publication: Equitable clique-coloring in claw-free graphs with maximum degree at most 4

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