Some bounds on the size of maximum G-free sets in graphs

DOI10.1142/S1793830922501324zbMATH Open1516.05179arXiv2201.04333OpenAlexW4291014513WikidataQ114071630 ScholiaQ114071630MaRDI QIDQ6174763FDOQ6174763

Authors: Yaser Rowshan 

Publication date: 15 July 2023

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

Abstract: For given graph $H$, the independence number $alpha(H)$ of $H$, is the size of the maximum independent set of $V(H)$. Finding the maximum independent set in a graph is a NP-hard problem. Another version of the independence number is defined as the size of the maximum induced forest of $H$, and called the forest number of $H$, and denoted by $f(H)$. Finding $f(H)$ is also a NP-hard problem. Suppose that $H=(V(H),E(H))$ be a graph, and $G$ be a family of graphs, a graph $H$ has a $G$-free $k$-coloring if there exists a decomposition of $V(H)$ into sets $V_i$, $i-1,2,ldots,k$, so that $GsubseteqH[V_i]$ for each $i$, and $GinG$. $SsubseteqV(H)$ is $G$-free, where the subgraph of $H$ induced by $S$, be $G$-free, i.e. it contains no copy of $G$. Finding a maximum subset of $H$, so that $H[S]$ be a $G$-free graph is a very hard problem as well. In this paper, we study the generalized version of the independence number of a graph. Also giving some bounds about the size of the maximum $G$-free subset of graphs is another purpose of this article.

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

Recommendations

• On \({\mathcal F}\)-independence in graphs
• Nordhaus–Gaddum problem in terms of G-free coloring
• The number of maximum independent sets in graphs
• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs
• The independence number in graphs of maximum degree three

zbMATH Keywords

independence numberforest number\(G\)-free coloring\(G\)-free subset

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Large induced forests in sparse graphs
• A new lower bound on the independence number of a graph and applications
• Decycling graphs
• Decycling numbers of random regular graphs
• On the maximum induced forests of a connected cubic graph without triangles
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Independence, odd girth, and average degree
• The forest number in several classes of regular graphs
• Graphs with unique maximum independent sets
• Title not available (Why is that?)
• The number of maximum independent sets in graphs
• The complexity of \(G\)-free colourability
• Nordhaus–Gaddum problem in terms of G-free coloring
• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs

Cited In (4)

• On \({\mathcal F}\)-independence in graphs
• Title not available (Why is that?)
• New exact values of the maximum size of graphs free of topological complete subgraphs
• Maximum cardinality neighbourly sets in quadrilateral free graphs

This page was built for publication: Some bounds on the size of maximum G-free sets in graphs

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