Cycle lengths and chromatic number of graphs (Q1883263): Difference between revisions

Let \(r(G)\) and \(s(G)\) be the number of odd and even cycle lengths in a graph \(G,\) respectively. It is shown that for each graph \(G\) its chromatic number satisfies \(\chi (G)\leq \min \{2r(G)+2,2s(G)+3\}.\)

0 references

Mathematics Subject Classification ID

05C15

0 references

0 references

0 references

graph

0 references

chromatic number

0 references

cycle length

0 references

reviewed by

Peter Horák

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.disc.2003.11.055

0 references

0 references

0 references

0 references

Graphs with \(k\) odd cycle lengths

0 references

Q3433915

0 references

Colouring Graphs with Prescribed Induced Cycle Lengths

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1883263

@@ Property / reviewed by @@
+Peter Horák
@@ Property / reviewed by: Peter Horák / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.disc.2003.11.055
+Normal rank
@@ Property / OpenAlex ID @@
+W2122560436
@@ Property / OpenAlex ID: W2122560436 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5422499
@@ Property / cites work: Q5422499 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3491635
@@ Property / cites work: Q3491635 / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs with \(k\) odd cycle lengths
@@ Property / cites work: Graphs with \(k\) odd cycle lengths / rank @@
+Normal rank
@@ Property / cites work @@
+Q3433915
@@ Property / cites work: Q3433915 / rank @@
+Normal rank
@@ Property / cites work @@
+Colouring Graphs with Prescribed Induced Cycle Lengths
+Normal rank