On coloring graphs with well-distributed edge density
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911096685723648 |
|---|---|
| author | Hassan, Syed Mujtaba Hussain, Shahid |
| author_facet | Hassan, Syed Mujtaba Hussain, Shahid |
| contents | In this paper, we introduce a class of graphs which we call average hereditary graphs. Many graphs that occur in the usual graph theory applications belong to this class of graphs. Many popular types of graphs fall under this class, such as regular graphs, trees and other popular classes of graphs. The paper aims to explore some interesting properties regarding colorings average hereditary graphs. We prove a new upper bound for the chromatic number of a graph in terms of its maximum average degree and show that this bound is an improvement on previous bounds. From this, we show a relationship between the average degree and the chromatic number of an average hereditary graph. We then show that even with new bound, the graph 3-coloring problem remains NP-hard when the input is restricted to average hereditary graphs. We provide an equivalent condition for a graph to be average hereditary, through which we show that we can decide if a given graph is average hereditary in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06803 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On coloring graphs with well-distributed edge density Hassan, Syed Mujtaba Hussain, Shahid Discrete Mathematics Computational Complexity Combinatorics 05C15, 05C42, 05C07 (Primary) 05C75, 05C69, 05C25 (Secondary) In this paper, we introduce a class of graphs which we call average hereditary graphs. Many graphs that occur in the usual graph theory applications belong to this class of graphs. Many popular types of graphs fall under this class, such as regular graphs, trees and other popular classes of graphs. The paper aims to explore some interesting properties regarding colorings average hereditary graphs. We prove a new upper bound for the chromatic number of a graph in terms of its maximum average degree and show that this bound is an improvement on previous bounds. From this, we show a relationship between the average degree and the chromatic number of an average hereditary graph. We then show that even with new bound, the graph 3-coloring problem remains NP-hard when the input is restricted to average hereditary graphs. We provide an equivalent condition for a graph to be average hereditary, through which we show that we can decide if a given graph is average hereditary in polynomial time. |
| title | On coloring graphs with well-distributed edge density |
| topic | Discrete Mathematics Computational Complexity Combinatorics 05C15, 05C42, 05C07 (Primary) 05C75, 05C69, 05C25 (Secondary) |
| url | https://arxiv.org/abs/2402.06803 |