On the b-chromatic number of regular graphs without 4-cycle

DOI10.1016/J.DAM.2012.02.001MaRDI QIDQ427905zbMATH OpenOpenAlexFDO

Authors Saeed Shaebani

Publication date 18 June 2012

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

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

zbMATH Keywords

\(b\)-chromatic numberdiametergirthvertex connectivity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40)

Abstract: The b-chromatic number of a graph $G$, denoted by $phi(G)$, is the largest integer $k$ that $G$ admits a proper $k$-coloring such that each color class has a vertex that is adjacent to at least one vertex in each of the other color classes. We prove that for each $d$-regular graph $G$ which contains no 4-cycle, $phi(G)geqlfloorfracd+32floor$ and if $G$ has a triangle, then $phi(G)geqlfloorfracd+42floor$. Also, if $G$ is a $d$-regular graph which contains no 4-cycle and $diam(G)geq6$, then $phi(G)=d+1$. Finally, we show that for any $d$-regular graph $G$ which does not contain 4-cycle and $kappa(G)leqfracd+12$, $phi(G)=d+1$.

Recommendations

• On the \(b\)-chromatic number of regular graphs
• The b-chromatic number of regular graphs via the edge-connectivity
• On the \(b\)-chromatic number of regular bounded graphs
• The b-chromatic number and f-chromatic vertex number of regular graphs
• \(b\)-coloring of the Mycielskian of regular graphs

Cites work

• Bounds for the b-chromatic number of G-v
• Bounds for the b-chromatic number of the Mycielskian of some families of graphs.
• Bounds for the b-chromatic number of vertex-deleted subgraphs and the extremal graphs
• Bounds for the b-chromatic number of some families of graphs
• Exact values for theb-chromatic number of a power completek-ary tree
• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• scientific article; zbMATH DE number 1919512 (Why is no real title available?)
• On \(b\)-coloring of the Kneser graphs
• On \(b\)-colorings in regular graphs
• On \(b\)-continuity of Kneser graphs of type \(\mathrm{KG}(2k+1,k)\).
• On approximating the b-chromatic number
• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-coloring of \(P_{4}\)-tidy graphs
• On the \(b\)-continuity property of graphs
• On the \(b\)-dominating coloring of graphs
• On the b-chromatic number of Kneser graphs
• On the b-coloring of cographs and \(P_{4}\)-sparse graphs
• Some bounds for the b-chromatic number of a generalized Hamming graph
• Some bounds for the b-chromatic number of a graph
• The b -chromatic number of the cartesian product of two graphs
• The b-chromatic number of a graph
• The b-chromatic number of cubic graphs
• The b-chromatic number of power graphs of complete caterpillars

Cited in

(10)

• The b-chromatic number and related topics -- a survey
• The \(b\)-continuity of graphs with large girth
• On the \(b\)-chromatic number of regular graphs
• Graphs of girth at least 7 have high \(b\)-chromatic number
• On the \(b\)-chromatic number of regular bounded graphs
• On the family of \(r\)-regular graphs with Grundy number \(r+1\)
• A characterization of b-chromatic and partial Grundy numbers by induced subgraphs
• The b-chromatic number of regular graphs via the edge-connectivity
• The b-chromatic number and f-chromatic vertex number of regular graphs
• \(b\)-chromatic number of lexicographic product of some graphs

This page was built for publication: On the \(b\)-chromatic number of regular graphs without 4-cycle

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