Nordhaus–Gaddum problem in terms of G-free coloring

DOI10.1142/S1793830922501142MaRDI QIDQ6132869zbMATH OpenOpenAlexFDO

Authors Yaser Rowshan

Publication date 15 July 2023

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

conditional chromatic number\(G\)-free coloring\(G\)-free criticalthe Nordhaus-Gaddum problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Let $H=(V(H),E(H))$ be a graph. A $k$-coloring of $H$ is a mapping $pi:V(H)longrightarrow1,2,ldots,k$, if each color class induces a $K_2$-free subgraph. For a graph $G$ of order at least $2$, a $G$-free $k$-coloring of $H$, is a mapping $pi:V(H)longrightarrow1,2,ldots,k$, so that the induced subgraph by each color class of $pi$, contains no copy of $G$. The $G$-free chromatic number of $H$, is the minimum number $k$, so that it has a $G$-free $k$-coloring, and denoted by $ch{i}_G(H)$. In this paper, we give some bounds and attributes on the $G$-free chromatic number of graphs, in terms of the number of vertices, maximum degree, minimum degree, and chromatic number. Our main results are the Nordhaus-Gaddum-type theorem for the $G$-free chromatic number of a graph.

Recommendations

• The Nordhaus-Gaddum problem for the \(k\)-defective chromatic number of a \(P_4\)-free graph
• scientific article; zbMATH DE number 500499
• Chromatic sums for colorings avoiding monochromatic subgraphs
• On the chromatic number of \(2 K_2\)-free graphs
• Extremal graphs in some coloring problems

Cites work

• scientific article; zbMATH DE number 3885934 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3358515 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs
• A survey of Nordhaus-Gaddum type relations
• Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers
• On Complementary Graphs
• On the Point-Arboricity of a Graph and its Complement

Cited in

(5)

• Some bounds on the size of maximum G-free sets in graphs
• scientific article; zbMATH DE number 1308944 (Why is no real title available?)
• Essentially disjoint families, conflict free colorings and Shelah's revised GCH
• The complexity of \(G\)-free colourability
• Chromatic sums for colorings avoiding monochromatic subgraphs

This page was built for publication: Nordhaus–Gaddum problem in terms of G-free coloring

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